11 June 2016

位操作

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)

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

i & (-i)

i = 00001100  =>  -i = 11110011  =>  lowbit(i) = 00000100

子集 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");
}


for (int i = 0; i < (1<<n); i++) {
   for (int j = 0; j < n; j++) {
       if ((i | (1<<j)) == i) {
           printf("%d ", 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 人