二进制
11 June 2016

补码

8 得到 -8

~8 + 1

-8 得到 8

~(-8) + 1

位操作

n 从 0 开始

设置第 n 位为 1(设置某些标志)

i = (i | (1 << n));

设置第 n 位为 0(取消某些标志)

i = (i & ~(1 << n));

反转第 n 位

i = (i ^ (1 << n));

判断第 n 位是否为 1

if ((i & (1 << n)) != 0) {
     return 1;
}

return 0;

去掉最后一位 1,即让一个数为偶数

i & (i-1)

i = 1111  =>  1110 => 1100 => 1000 => 0000

得到最后一个 1 (这个的术语叫 lowbit)

i & (-i)

(i = 001100  =>  -i = 110100  =>  lowbit(i) = 000100)

i = 1111 => 1
i = 1100 => 0100
i = 1000 => 1000

判断某个数是否是 2 的 n 次方

n > 0 && (n & (n-1)) == 0

子集 O(2^n)

int n = 4;      // 集合为: {0 1 2 3}

for (int i = 0; i < (1<<n); i++) { // 从 0 到 15
    for (int j = 0; j < n; j++) {   // 从 0 到 3
        if ((i & (1<<j)) != 0) {    // 如果发现对应的 bit 位设置了
            printf("%d ", j);
        }
    }
    printf("\n");
}


// 举例
int n = 4;

char str[] = "abcd";

for (int i = 0; i < (1<<n); i++) {
    for (int j = 0; j < n; j++) {
        if ((i & (1 << j)) != 0) {
            printf("%c", str[j]);
        }
    }
    printf("\n");
}

做统计 (统计 3 天之内有上线的人数)

redis> setbit day1 10 1        # 第 1 天,user_id 为 10 的用户登陆过
redis> setbit day1 20 1        # 第 1 天,user_id 为 20 的用户登陆过

redis> setbit day2 30 1        # 第 2 天,user_id 为 30 的用户登陆过
redis> setbit day2 23 1        # 第 2 天,user_id 为 20 的用户登陆过

redis> setbit day3 40 1        # 第 3 天,user_id 为 40 的用户登陆过
redis> setbit day3 10 1        # 第 3 天,user_id 为 10 的用户登陆过


redis> bitop or res day1 day2 day3
redis> bitcount res            # 5 人