整数的二进制表达中有多少个1

整数的二进制表达中有多少个1

统计整型的二进制表达中1的个数

【题目】
给定一个整型(32位整数)n，可为0，可为正，也可为负，返回该整型二进制表达中1的个数。

无符号右移

算法思路：每次无符号右移时统计整型n为1的次数。

注意：python无符号运算，非负数有符号移位运算和无符号运算相同，因此需额外处理负数的无符号移位运算，将其转换为可以间接求的正数。
方法1：
$\because -n= \sim n+1 \\ \therefore \sim n= -n-1$∵−n=∼n+1∴∼n=−n−1
负数1的个数可以转换为(其相反数-1)中0的个数, 即32 - (转换数中1的个数)；

方法2：将负数转换为对应的无符号整数即$n+2^{32}$n+232，在统一移位计算1的个数；

相应代码

# 负数转换为(相反数-1)中0的个数, 32 - (1的个数)
def count_one1(n):
    if n < -2 ** 31 or n > 2 ** 31 - 1:
        return
    if n == -2 ** 31:
        return 1
    elif n >= 0:
        count = 0
        while n != 0:
            count += n & 1
            n = n >> 1
        return count
    else:
        count = 0
        n = -n - 1
        while n != 0:
            count += n & 1
            n = n >> 1
        return 32 - count

# 统一转换成无符号数(0 ~ 2 ^ 32 - 1)
# 负数 + 2 ^ 32
def count_one2(n):
    if n < -2 ** 31 or n > 2 ** 31 - 1:
        return
    if n < 0:
        n += 2 ** 32
    count = 0
    while n != 0:
        count += n & 1
        n = n >> 1
    return count

按位与移除最右侧1

算法思路：
方法3：n & (n - 1)移除最右侧的1，统计移除次数；
方法4：n & (~n + 1)获取最右侧的1，原数相减获取最右侧的1即移除最右侧的1，统计移除次数；

注意：
n & (n - 1)移除最右侧的1和n & (~n + 1)获取最右侧的1是位运算常用技巧。
实际上两者等价，简单证明如下。
$n - (n \; \& \; (n - 1) \,) = n \; \& \; (0Xffffffff - n + 1) = n \; \& \; (\sim n + 1)$n−(n&(n−1))=n&(0Xffffffff−n+1)=n&(∼n+1)

相应代码

# n & (n - 1)逐个移除最右侧1，统计1的个数
def count_one3(n):
    if n < -2 ** 31 or n > 2 ** 31 - 1:
        return
    count = 0
    while n != 0 and n != -2 ** 31:
        n = n & (n - 1)  # 移除最右侧1
        count += 1
    if n == -2 ** 31:
        count += 1  # 统计符号位1
    return count

# n & (~n + 1)获取最右侧1，统计1的个数
def count_one4(n):
    if n < -2 ** 31 or n > 2 ** 31 - 1:
        return
    count = 0
    while n != 0 and n != -2 ** 31:
        n -= n & (~n + 1)  # 移除最右侧1
        count += 1
    if n == -2 ** 31:
        count += 1  # 统计符号位1
    return count

平行算法

算法思路：
四次$(n ; & ; c_i) +(,(n >> i , ) ; & ; c_i) $
登峰造极之操作，大家可略微了解，加强对位运算的理解。
以-1为例，将十六进制以二进制展开，帮助大家更好地理解其中的奥妙。
$r_0 \; \;:1111 \, 1111 \, 1111 \, 1111 \, 1111 \, 1111 \, 1111 \, 111\underline{1} \\ c_1 \; \;: 0101 \, 0101 \, 0101 \, 0101 \, 0101 \, 0101 \, 0101 \, 01\underline{01} \\ r_1 \; \;: 1010 \, 1010 \, 1010 \, 1010 \, 1010 \, 1010 \, 1010 \, 10\underline{10} \\ c_2 \; \;: 0011 \, 0011 \, 0011 \, 0011 \, 0011 \, 0011 \, 0011 \, \underline{0011} \\ r_2 \; \;: 0100 \, 0100 \, 0100 \, 0100 \, 0100 \, 0100 \, 0100 \, 0\underline{100} \\ c_3 \; \;: 0000 \, 1111 \, 0000 \, 1111 \, 0000 \, 1111 \, \underline{\color{#0000FF}{0}000} \, \underline{\color{#0000FF}{1}111} \\ r_3 \; \;: 0000 \, 1000 \, 0000 \, 1000 \, 0000 \, 1000 \, 0000 \, \underline{1000} \\ c_4 \; \;: 0000 \, 0000 \, 1111 \, 1111 \, \underline{\color{#0000FF}{0000}} \, \underline{0000} \, \underline{\color{#0000FF}{1111}} \, \underline{1111} \\ r_4 \; \;: 0001 \, 0000 \, 0001 \, 0000 \, 0001 \, 0000 \, 000\underline{1} \, \underline{0000} \\ c_5 \; \;: \underline{\color{#0000FF}{0000}} \, \underline{\color{#0000FF}{0000}} \, \underline{\color{#0000FF}{000}0} \, \underline{0000} \, \underline{\color{#0000FF}{1111}} \, \underline{\color{#0000FF}{1111}} \, \underline{\color{#0000FF}{111}1} \, \underline{1111} \\ r_5 \; \;: 0000 \, 0000 \, 0000 \, 0000 \, 0000 \, 0000 \, 00\underline{10} \, \underline{0000} \\$r0​:11111111111111111111111111111111​c1​:01010101010101010101010101010101​r1​:10101010101010101010101010101010​c2​:00110011001100110011001100110011​r2​:01000100010001000100010001000100​c3​:0000111100001111000011110000​1111​r3​:00001000000010000000100000001000​c4​:00000000111111110000​0000​1111​1111​r4​:0001000000010000000100000001​0000​c5​:0000​0000​0000​0000​1111​1111​1111​1111​r5​:0000000000000000000000000010​0000​
的确费了很大功夫，我来解释下运算的原理及过程。
$r_0$r0​为初始值，这里为-1。
$(n ; & ; c_i) +(,(n >> i , ) ; & ; c_i) $在错位统计$2^i$2i组1的个数，并合并累积到大组$r_i$ri​中。
$c_i$ci​为第i次操作的常数项
  划横线的是本质上起作用的位置，再扩展至32位，即为整个$c_i$ci​
  蓝色部分的所在的位置表示可取0，可取1，常数项可以修改
$r_i$ri​为第i次运算的结果值，$r_5$r5​为最终统计1的数量。

相应代码

最终以如图所示的常数进行运算，与左神书上一致。

# 平行算法
# 对负数有符号右移转换正数无符号右移处理
# 换常数进行测试
def count_one5(n):
    if n < -2 ** 31 or n > 2 ** 31 - 1:
        return
    if n < 0:
        n += 2 ** 32
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555)
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
    n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f)
    n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff)
    n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff)
    return n

测试代码

以无符号右移代码为例，进行测试，其他测试用例相同。

# 简单测试
if __name__ == '__main__':
    n = 0
    print(count_one1(n))  # 0
    n = 3
    print(count_one1(n))  # 2
    n = -1
    print(count_one1(n))  # 32
    n = -3
    print(count_one1(n))  # 31

小结

位运算考察整数进制的表示和理解，建议拿笔和纸带入用例推导一番，加强训练。

有任何疑问和建议，欢迎在评论区留言和指正！

感谢您所花费的时间与精力！