ACW07-位运算

The bit operation

Posted by qingshan on May 12, 2019

ACW位运算算法07: 801. 二进制中1的个数

给定一个长度为 n 的数列,请你求出数列中每个数的二进制表示中 1 的个数。

输入格式 第一行包含整数 n。

第二行包含 n 个整数,表示整个数列。

输出格式 共一行,包含 n 个整数,其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。

数据范围 1≤n≤100000, 0≤数列中元素的值≤1e9

1
2
3
4
5
输入样例:
5
1 2 3 4 5
输出样例:
1 1 2 1 2

思路: lowbit

** 用于找到一个整数二进制中最后一个 1 的位置,连同此位置后面的 0,输出整数 ** 步骤:

  1. 先取反: -x = ~x+1 (反码+1,解释:~x = -x - 1)
  2. 再拿-x 和 x 进行“与”运算: x & -x
  3. 输出结果即是 lowbit,因为其他相同位都抵消了

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def lowbit(x):
    return x & -x
    # -x = ~x-1

def main():
    n = int(input())
    a = list(map(int, input().split()))

    for i in a:
        res = 0 # 结果:1 出现的次数
        while i != 0:
            i -= lowbit(i)  # 将 i 减去它本身的 lowbit,多次后就会变成 0
            res += 1
        print(res, end=" ")

if __name__ == "__main__":
    main()


知识点

原码

原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 比如如果是8位二进制:

[+1]原 = 0000 0001 [-1]原 = 1000 0001

  • 第一位0 正数;第一位 1 负数

反码

反码的表示方法是:

** 正数的反码是其本身 **

负数的反码是在其原码的基础上, 符号位不变,其余各个位取反.

[+1] = [00000001]原 = [00000001]反 [-1] = [10000001]原 = [11111110]反 可见如果一个反码表示的是负数, 人脑无法直观的看出来它的数值. 通常要将其转换成原码再计算.

补码

补码的表示方法是:

** 正数的补码就是其本身 **

负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)

[+1] = [00000001]原 = [00000001]反 = [00000001]补 [-1] = [10000001]原 = [11111110]反 = [11111111]补

对于负数, 补码表示方式也是人脑无法直观看出其数值的. 通常也需要转换成原码在计算其数值.