一个二进制数中有多少个1

我只能想到用移位消去最小的1的方法

时间复杂度为i中1的个数的做法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

    public int hammingWeight(int n) {
        int ans=0;
        while(n!=0){
            
            ans++;
            n=n&(n-1);
            
        }
        return ans;
    }

java 本身也提供了这个方法，所以就来看看底层的源码。 这个方法非常有意思，我已经被迷住了，源码的分析部分来自于

https://blog.csdn.net/weixin_42092787/article/details/106607426

1
2
3
4
5
6
7
8
9

public static int bitCount(int i) {
     // HD, Figure 5-2
     i = i - ((i >>> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
     i = (i + (i >>> 4)) & 0x0f0f0f0f;
     i = i + (i >>> 8);
     i = i + (i >>> 16);
     return i & 0x3f;
}

简单来说，源码非常非常巧妙的利用了 位运算的性质，大概我这辈子也想不到吧。

我们从最后的落脚点出发，或许更能理解这种思路：

return i & 0x3f; 0x3f 十六进制转为二进制是：

十六进制 二进制 0x3f 00 00 00 00 00 00 00 00 00 00 00 00 00 11 11 11 这时候我们想一下这行代码，对于 0x3f 来说，它和变量 i 做 与 运算，得到的最大结果也就是 0x3f 本身，也就是二进制 111111 ，对应 十进制是 63。

这是什么意思呢？

对于 输入 n ，即使这个数字的二进制表达占满了 32 位比特 且全都是 1，那么这条语句的功能，数 1 的个数，结果最多也就是 32 ，对应二进制表达是 100 000，长度为 6 位。

所以这一点上，这种方法的计算过程保证了有效位足够，另一方面保证，最终返回的是 前面计算结果的最后六位的值，去掉了高位上面的干扰。

而这整个代码也都是基于这种思想的，逐渐缩小有效位的范围

我们先总结一下代码中的十六进制数：

十六进制 二进制 0x55555555 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 0x33333333 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11 0x0f0f0f0f 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 接着一行一行来看代码。

第一行代码 i = i - ((i >>> 1) & 0x55555555); 我直接告诉你，它完成的功能叫做，每两位进行一次统计，统计 1 的个数，并把结果放在对应的原来位置上。

1. i »> 1 是将 i 无符号右移一位

2. 0x55555555 是 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01

3. 右移后 和 0x55555555 进行按位与操作

4.再用 i 减去 “3” 的结果

上面的 “1” 想一想：对于一个 32 位的数 i ，右移一位之后，第 2、4、6、……、32位的数字，分别跑到了第 1、3、5、……、31位上，也就对应到了 0x55555555 的 所有 1 的位置。

上面的 “2” 和 “3” i 在右移之后和 0x55555555 进行 与 操作，就会得到原来 i 的第 2、4、6、……、32 位上的所有真实的值；同时，第 1、3、5、……、31位上的值都和 0 进行与操作之后变成了0。（到这里还看不出这么做的意义，别着急，看下一步）

上面的 “3” 重点来了，接着用 i - （2 和 3 的结果）会发生什么事？

一个二进制两位的数字，可能的形式有：00,01,10,11. 右移之后分别和 01 进行与运算，得到： 00,00,01,01. 用原来的数减去右移后的，就能够得到： 00,01,01,10.

观察一下结果可以发现：每两位的数值 就表示了以前这两位上 有 1 的个数

（这里可以回头想一想，先和0x55555555 进行 与 操作是非常必要的，因为如果仅仅右移，第 3 位如果有 1，右移之后会占用第二位，会影响统计结果，因此必须把这些位都通过和 0 的与操作清零。）

第二行代码 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); 第二行和第一行的本质思路是一样的，进一步扩大范围，统计原始 i 每 4 位上 1 的个数。

1. 0x33333333 是 00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11

2. i 和 0x33333333 进行按位与操作

3. i 右移两位，再和 0x33333333 进行按位与操作

4.将 “ 2 ” 和 “ 3 ” 的结果相加

上面的 “1” 和 “2” 和 0x33333333 进行 与 操作，就会得到第一行代码运行之后 的第 1 2、5 6、9 10、……、29 30 位上的所有真实的值；同时，第 3 4、7 8、11 12、……、31 32位上的值都和 00 与之后变成了00。

上面的 “3” 和只有 两位 的二进制数的减法性质不同，所以这里不能再使用减法。 那么丢掉的那一半位置的数字还是需要找回来的。怎么办呢

i 右移两位，第 3 4、7 8、11 12、……、 31 32 位上的值跑到了 第 1 2、5 6、9 10、……、 29 30位上。此时再做了一边和 “2” 一样的事情，这就得到了第一行代码运行之后的第 3 4、7 8、11 12、……、 31 32 位上的真实的值。

上面的 “4” 简单相加，功能完成。（直接相加不用考虑进位吗？答案是不用，原来的数字 每四位上面 1 的个数最多是 4 个，对应成二进制是 100 ，只会占用 3 个二进制位。）

可以回头想想。源数字 i 的 每四位上面 1 的个数，已经被统计出来了，替换在了对应的位置上。

第三行代码 i = (i + (i >>> 4)) & 0x0f0f0f0f; 这一步，要开始统计 原始数字 i 每 8 位上面 1 的个数。我们可以看到代码的方式又变了。 （和第二行写法不一样，但其实第三行可以写成和第二行一样的格式；第二行却不能写成第三行这样的形式，大家可以想想为什么）

1. 将 i 右移四位，再与 i 相加

2.0x0f0f0f0f 的二进制表达是 0000 1111 0000 1111 0000 1111 0000 1111

3.将第一步的结果 和 0x0f0f0f0f 进行与操作

上面的 “1” 对其相加个数的时候，显然要以低位为准，所以第 5 6 7 8 、13 14 15 16、20 21 23 24、29 30 31 32 位的数字，挪到了 1 2 3 4 、 9 10 11 12、17 18 19 20 、25 26 27 28 位上，对应相加。

这里的加和，最多不会超过 8 ，对应二进制是 1000，（因为源数字 i 每 8 位上面 1 个数不会超过 8）所以直接加也不会产生错误。

上面的 “2” 和“3” 和 0x0f0f0f0f 进行 与 操作，就会得到源数字 i 每 8 位上面 1 的个数，存储在了第 1 2 3 4 、 9 10 11 12、17 18 19 20 、25 26 27 28位上。而第 5 6 7 8 、13 14 15 16、20 21 23 24、29 30 31 32 位一定是 0.

第四行和第五行代码

1
2

i = i + (i >>> 8);
i = i + (i >>> 16);

这两行，完成的是一个功能，也就是把源数字 i 每 16 位上面 1 的个数，存储在了 116位上。（此时没有做第1732位的清零）

当然，如果按照前几步的思路，你当然可以把这两行代码替换成：

i = i + (i >>> 8) & ‭FF00FF‬; 这行是我想的，但经过验证可以达到一样的效果，因为 ‭FF00FF‬ 的二进制表达是： ‭0000 0000 1111 1111 0000 0000 1111 1111‬

不过显然原作者的做法更巧妙，毕竟直接右移16位就能达到效果。

第六行代码 return i & 0x3f; 回到最开始我们对这一步的分析，源数字 i 作为32位二进制数字，1 的个数就最多 32 而已。

那么代码的意义显而意见。 最终就会返回 原始输入 i 的二进制形式上 1 的个数。

总结一下，如果这道题交给我们来做，即使是位运算，按位与 和 用了 n&(n-1) 这两种方法，最差的情况下都是要运行 32 次位运算的，但是底层源码的方法，却是恒定只进行 6 次计算。不得不说真实优秀。

相信我讲的很清楚了，希望对大家有帮助。（苦心成果，转载请标明出处 ———————————————— 版权声明：本文为CSDN博主「JohnArchie」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/weixin_42092787/article/details/106607426

我的理解

第一行代码：将每两位的 1 的个数统计，并把结果每两位保存，例如1101一个有3个1，高2位(11)中1的个数为2(01)，低2位(01)的个数为1(01),最后保存的结果为0101 i=0010010100101011

0001001010010101 (i»>1)

0001000000010101(i»>1&0x5555555)

0001010100010110

第二行代码：将将每4位的 1 的个数统计，并把结果每4位保存

0001010100010110(i)

0000010101000101(i»>2)

0011001100110011

0000000100000001(i»>2&0x3333333333)

0001000100010010(i&0x333333333)

0001001000010011

相当于对i=0001010100010110每隔两位提出来：

0001000100010010(i&0x333333333)

0001001000010011

每4位得到四位 的1的值

第三行代码：将将每8位的 1 的个数统计，并把结果每8位保存

0000111100001111

0000001100000100

每8位表示8位 的1的数量

0000000000000011(i»>8)

0000000000000100

0000000000000111

这样就得到一共有7个1.

异或的性质：

110=100^10

观察这三个数110 100 10

任意两个异或的结果是另外一个数：

110^100=10

110^10=100

1720. 解码异或后的数组

难度简单80

未知 整数数组 arr 由 n 个非负整数组成。

经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。

给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。

请解码返回原数组 arr 。可以证明答案存在并且是唯一的。

示例 1：

输入：encoded = [1,2,3], first = 1 输出：[1,0,2,1] 解释：若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

示例 2：

输入：encoded = [6,2,7,3], first = 4 输出：[4,2,0,7,4]

提示：

  • 2 <= n <= 104
  • encoded.length == n - 1
  • 0 <= encoded[i] <= 105
  • 0 <= first <= 105
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int[] decode(int[] encoded, int first) {
        int n=encoded.length;
        int []ans=new int[n+1];
        ans[0]=first;
        for(int i=1;i<n+1;i++){
            ans[i]=encoded[i-1]^ans[i-1];
        }
    return ans;
    }
}

还有一题：

371. 两整数之和

难度中等425

不使用运算符 + 和 - ，计算两整数 a 、b 之和。

示例 1:

输入: a = 1, b = 2 输出: 3

示例 2:

1
2

输入: a = -2, b = 3
输出: 1

通过次数54,177

提交次数93,386

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int getSum(int a, int b) {
        System.out.println(a+" b="+b);
        int xor=a^b;
        int and=(a&b)<<1;
         System.out.println(and);
        if(and!=0) xor=getSum(xor,and);
        return xor;
    }
}

2023-8-4更新

今天混迹知乎，又看到一个答案，原来popcnt是有cpu指令的，愚蠢的程序员的这些小心思，最后都能让编译器收拾烂摊子。

开-O2 -mpopcnt，聪明的编译器知道你想算popcnt，直接给你生成x86指令了，你也可以用gcc的内联函数直接生成popcnt指令 int __builtin_popcount (unsigned int x);，自 GCC 3.4 版本（2004年）。如果你的机器架构支持的话，会直接译成一条CPU指令。

Linux可以使用cat /proc/cpuinfo | grep popcnt查看你的cpu是否支持这一条指令

https://www.zhihu.com/question/444266754/answer/1729863823

最后，抛出一个问题，在程序中计算多少个1的频率高吗？是否真的需要专用的硬件来实现，编译器的适配又如何呢？