位运算

[TOC]

位运算：总共只有与、或、异或、左移和右移5种位运算

n/2 与 n >> 1 , 除法的效率比移位运算要低得多。

练习

试题15:二进制中1的个数

题目:题目:输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。例如,把9表示成二进制是1001,有2位是1。因此, 如果输入9, 该函数输出2。

// 负数的补码是`反码+1`。
// 通过左移参考位 flag 实现
func NumberOf1(n int ) int {
    count := 0
    flag := uint32(1)

    for flag > 0 {
        if uint32(n) & flag > 0 {
            count++
        }
        flag = flag << 1
    }
    return count
}

解法二：（推荐学习）

func NumberOf(n int ) int {
    count := 0
    x := uint32(n)
    for x > 0 {
        count++
        x = (x - 1) & x  // x 与 x-1进行与运算，可以把x 的最有边的1变为 0
    }
    return count
}

x 与 x-1进行与运算，可以把x 的最有边的1变为 0。比如x 为 1100 ，x - 1 就是 1011 。1100 & 1011 = 1000 。所以每次 执行 x = (x - 1) & x 都相当于把 x 的最右边1变为了0。