剑指offer之二进制中1的个数

1 问题

实现一个函数,输入一个函数,输出该二进制数据中1的个数。例如9表示二进制数据1001,有2位是1,因此输入9,该函数会输出2。

2 分析

我们先了解下计算机里面位运算,有5种

1)& 这个是与操作,规律如下

1 & 1 = 1     1 & 0 = 0     0 & 1= 0    0 & 0 = 0

2)| 这个是或运算,规律如下

1 | 1 = 1     1 | 0 = 1     0 | 1= 1    0 | 0 = 0

3)^ 异或运算,规律如下

1 ^ 1 = 0     1 ^ 0 = 1      0 ^ 1 = 1     0 ^ 0 = 0 

4) 左移 m<<n 表示把m左移n位,在左移n位的时候,最左边的n位丢弃,同时右边补上n个0 比如

00001010 << 2 = 00101000

10001010 << 3 = 01010000

5) 右移 左移 m >> n 表示把m右移n位,在右移n位的时候,最右边补上n个0 ,最左边分2种情况,如果数字是一个无符号整形

则用0填补最左边的n位,如果是一个有符号的数据,则最左边用数字的符号填补n个数据。如果是正数,左边补n个0,是负数左边补n个1.

00001010 >> 2 = 00000010

10001010 >> 3 = 11110001

这里我们可以把原数据和1进行&操作,如果二进制数据尾巴进行&操作,如果包含1的话&1操作就是1,返之结果为0,然后我们把数据进行右移一位就行。

如果一个正数要除以2,我们效率最高的是把这个数据进行右移一位。

3 代码实现

C++版本

#include <stdio.h>

/*
 *二进制数据里面包含数字1的个数
 */
int containOneNumber(int value)
{
    int count = 0;
    while (value != 0)
    {
        //这里是(value & 1)不是(value  & 0)
        if (value & 1)
            ++count;
        //这里是value = value >> 1,而不是value >> 1; 我们要用变量接收它
        //不然不管就只执行了一次也就是value除以了2,所以导致死循环。
        value = value >> 1;
    }
    return count;

}

int main(void)
{
    int result = containOneNumber(9);
    printf("result is %d\n", result);
    return 0;
}

java版本

public int containOneNumber(int value)
    {
        int count = 0;
        while (value != 0)
        {
            if ((value & 1) != 0)
            {
                count++;
            }
            value = value >>> 1; //>>>就是java中的无符号右移
        }
        return count;
    }

我们知道java用 >>> 是无符号右移,右移的时候,所以最高位左边都是0,如果这个数是负数的时候,右移的话最高位会补1,

C++版本就会变成死循环。

4 优化

方法1:

n与1做与运算,判断n的最低位是不是为1,接着把1左移一位得到2,再和n做与运算,就能判断n的次低位是不是1….这样反复左移

int containOneNumber1(int n)
{
    int flag = 1;
    int count = 0;
    while (flag != 0)
    {
        if ((flag & n) != 0)
        {
            count++;
        }
        flag = flag << 1;
    }
    return count;
}

方法2:

把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0,那么一个整数的二进制表示中有
多少个1,就可以进行多少次这样的操作

int containOneNumber1(int n)
{
    int flag = 1;
    int count = 0;
    while (n != 0)
    {
        ++count;
        n =  n & (n - 1);
    }
    return count;
}

5 总结

1) 把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0,那么一个整数的二进制表示中有多少个1

2)n与1做与运算,判断n的最低位是不是为1,接着把1左移一位得到2,再和n做与运算,就能判断n的次低位是不是1….这样反复左移

3) 如果是正整数的情况下,我们可以把正整数右移动和1进行&操作,然后再去统计。

(0)

相关推荐

  • C语言基础丨运算符之位运算符(六)

    对于更多紧凑的数据,C 程序可以用独立的位或多个组合在一起的位来存储信息.文件访问许可就是一个常见的应用案例.位运算符允许对一个字节或更大的数据单位中独立的位做处理:可以清除.设定,或者倒置任何位或多 ...

  • 【面试常考】位运算介绍与经典例题总结

    原创公众号:bigsai 原创不易,如果有收获请不要吝啬你的赞赞! 文章已收录在 全网都在关注的数据结构与算法学习仓库 欢迎star 前言 位运算隐藏在编程语言的角落中,其神秘而又强大,暗藏内力,有些 ...

  • 不使用+或-运算符,计算两数之和

    引言标在我们为了提升自身编程能力刷题时,总会总会遇到一些奇怪的要求,如:不使用+.-运算符计算两数之和.今天我们就可以通过位运算来解决这个问题.问题描述给你两个整数 a 和 b ,不使用 运算符 + ...

  • 每日一题 剑指offer(二叉搜索树的后序遍历序列)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题 剑指offer(二维数组中的查找)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 剑指offer之二维数组中查找

    剑指offer之二维数组中查找

  • 剑指offer之二叉搜索树的第K个节点

    剑指offer之二叉搜索树的第K个节点

  • 剑指offer之二叉搜索树和双向链表

    剑指offer之二叉搜索树和双向链表

  • 二进制中1的个数问题 (超详细)

    整数 二进制中1的个数 前两天遇到这个问题,第一反应就是%2和>>1这两个操作.   大概思路:   正数:%2,拿到原码(补码)的最右位,对于一个int类型的数进行32次判断,这是比较简 ...

  • 【剑指Offer】数值的整数次方

    题目描述 给定一个double类型的浮点数base和int类型的整数exponent.求base的exponent次方. 保证base和exponent不同时为0 解法1 最直接的思路,计算base的 ...

  • 【剑指Offer】链表中倒数第k个结点

    题目描述 输入一个链表,输出该链表中倒数第k个结点. 解法 基本思路是使用两个辅助指针p, q,让p先走k - 1步后,p, q两个指针再一起走 这样当p指针走到链表的末尾时,q指针刚好走到的就是倒数 ...

  • 【剑指Offer】反转链表

    题目描述 输入一个链表,反转链表后,输出新链表的表头. 解法1 可以使用三个辅助指针pHead, last,next pHead记录当前节点,last记录上一个节点,next记录下一个节点 首先使用n ...