【剑指Offer】T15 二进制中1的个数(二进制)

输入一个整数,输出该数二进制表示中 1 的个数。其中负数用补码表示。例如,输入 9,二进制位 1001,输出 2
思路 1:输入的 n 不断右移,和 00...01 做与运算&

  • 结果为 1:最后一位为 1
  • 结果为 0:最后一位为 0

循环停止条件:移位一直到整数变成 0。

注:除 2 运算等同于右移一位,但是位运算效率比较高

缺点:如果输入负数,移位后最高位会变成 1。一直右移会变成全 1,死循环。

补充:求 - 3 的十六进制:3 的十六进制为 0003,3 求反之后是 C,再加 1(补码),成 D,所以 - 3 的十六进制就是:FFFD

思路 2:把右移 n 变为左移000..001->000...010,再与 n 做与运算。

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

循环次数为整数二进制的位数 32。(强制循环 32 次结束,因为unsigned int最大长度为 32)

== 最优解:== 一个整数减 1,在和原整数与运算,会把整数最右边的1变成0。那么一个整数的二进制表示有多少个 1,就可以进行这样的操作。

例如:

  • 1100 - 1 = 10111100 & 1011 = 1000
  • 1000 - 1 = 00111000 & 0011 = 0000
int Number(int n){
    int count = 0;
    while(n){
        count++;
        n = (n - 1)&n;
    }
    return count;
}

拓展:

  • 一条语句判断整数是不是 2 的整数次方。
    • 如果是 2 的整数次方,那么二进制表示有且仅有一位是 1,其余都为 0。所以if(n & (n - 1) == 0){}
  • 两个整数 m、n,计算改变 m 的二进制多少位可以得到 n。
    1. 求两个数的异或
    2. 统计结果中 1 的位数
  • 右移替代除二运算、位与替代求余运算判断技术还是偶数
    • 4 & 1 -> 0 偶数
    • 5 & 1 -> 1 奇数

本文链接:https://ariser.cn/index.php/archives/156/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!