算法-位运算

1
2
3
4

// 6  0b0110
// 10 0b1010
// 2  0b0010
(6 & 10) == 2;

1
2
3
4

// 6  0b0110
// 10 0b1010
// 15 0b1110
(6 | 10) == 14;

1
2
3
4

// 只考虑最后 4 位
// 6  0b0110
// 9  0b1001
(~6 & ((1 << 4) - 1)) == 9;

1
2
3
4
5
6

// 6  0b0110
// 10 0b1010
// 12 0b1100
(6 ^ 10) == 12;
x ^ x == 0;
x ^ 0 == x;

1
2
3
4
5

// 6  0b0110
// 12 0b1100
(6 << 1) == 12;
// x *= 2;
x <<= 1;

1
2
3
4
5

// -11 0xfffffff5
// -6  0xfffffffa
(-11 >> 1) == -6;
// x > 0 && x /= 2;
x >>= 1;

1
2
3

// -11        0xfffffff5
// 2147483642 0x7ffffffa
(-11 >>> 1) == 2147483642;

1
2
3
4

// 奇数 x % 2 == 1
(x & 1) == 1
// 偶数 x % 2 == 0
(x & 1) == 0

1
2
3
4
5
6

// 将最低位 1 置 0
x > 0 && (x & (x - 1)) == 0
// 只保留最低位 1
x > 0 && (x & -x) == x
// 是否为因数
x > 0 && (1 << 31) % x == 0

1
2
3
4
5
6

// 转大写 (char) (c - 'a' + 'A')
c &= 95
// 转小写 (char) (c - 'A' + 'a')
c |= 32
// 大/小写互相转换
c ^= 32

1
2
3
4
5
6

// a' == a ^ b
// b' == b ^ a'  == b ^ a ^ b == a
// a' == a' ^ b' == a ^ b ^ a == b
a ^= b;
b ^= a;
a ^= b;

1
2
3
4

// 0b0... ^ 0b1... == 0b1...
// 0b0... ^ 0b0... == 0b0...
// 0b1... ^ 0b1... == 0b0...
a ^ b > 0;

1
2
3
4

//           n == 0b...10...0
//       n - 1 == 0b...01...1
// n & (n - 1) == 0b...000000
n & (n - 1);

1
2
3
4
5

//                n == 0b.....10...0
//            n - 1 == 0b.....01...1
//      n & (n - 1) == 0b.....000000
// n -= n & (n - 1) == 0b0...010...0
n -= n & (n - 1);

1
2
3
4
5

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

1
2
3
4

//    -n == (~n) + 1
// -(~n) == (~(~n)) + 1
// -(~n) == n + 1
n = -(~n);

1
2
3
4
5

//    -n == (~n) + 1
// -(-n) == (~(-n)) + 1
//     n == (~(-n)) + 1
// ~(-n) == n - 1
n = ~(-n);

1
2
3
4
5
6
7
8

// 12345678 -> 21436587
x = (x & 0x55555555) << 1 | (x >>> 1) & 0x55555555;
// 21436587 -> 43218765
x = (x & 0x33333333) << 2 | (x >>> 2) & 0x33333333;
// 43218765 -> 87654321
x = (x & 0x0f0f0f0f) << 4 | (x >>> 4) & 0x0f0f0f0f;
// 1B 2B 3B 4B -> 4B 3B 2B 1B
x = (x << 24) | ((x & 0xff00) << 8) | (x >> 8) & 0xff00 | (x >>> 24);

1

(x >> n) & 1

1

x | (1 << n)

1

x & (~(1 << n))

1

x & (~0 << n)

1

x | ((1 << (n + 1)) - 1)

1

(x >> (32 - n)) & 1