位操作相关

1.常见操作

1.1 检测数n的第k位是否为1

n & (1 << (k - 1))

1.2 将n的第k位置为1

n | (1 << (k - 1))

1.3 将n的第k位清零

n & ~(1 << (k - 1))

1.4 判断两个整数是否异号

x ^ y < 0 异号 否则同号

1.5 交换两个数

a ^= b;
b ^= a;
a ^= b;

1.6 消除n的二进制表示中最后一个1

n & (n - 1)

1.7 检查某个数是否是2的幂

如果是2的幂，只有一个1

n & (n - 1) == 0 ? true : false

2.例题

给定一个数n，计算其二进制表示1的个数

方法1：按位处理

当n不为0时，每次将n和1做与运算，然后将n右移一位

时间复杂度O(n)

int count = 0;
while (n != 0) {
	count += n & 1;
	n >>= 1;
}

方法2：取模

时间复杂度O(logn)

int count = 0;
while (n != 0) {
	if (n % 2 == 1) count++;
	n = n / 2;
}
return count;

方法3：

时间复杂度O(k)

int count = 0;
while (n != 0) {
	n = n & (n - 1);
	count++;
}
return res;