bit-operator

0.基础

& \ ^
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0

1.变量交换（无临时变量）

1
2
3
4
5
6
x = 0x10111101;
y = 0x00101110;

x = x ^ y;
y = x ^ y;
x = x ^ y;

(x ^ y) ^ y = x

Poor at exploiting instruction-level parallelism(ILP)

2.取两数的较小值

1
2
3
4
5
6
7
8
9
10
if (x < y)
{
    r = x;
}
else
{
    r = y;
}

r = (x < y) ? x : y;

A mispredicted branch empties the processor pipeline
• ~16 cycles on the cloud facility’s Intel Core i7’s.
The compiler might be smart enough to avoid the
unpredictable branch, but maybe not.

无分支获取取最小值

1
r = y ^ ((x ^ y) & -(x < y));

  • x < y, -(x < y) = -1, -1的二进制的所有位为1，(x ^ y) & -1 = (x ^ y), y ^ (x ^ y) = x

  • x > y, -(x < y) = 0, (x ^ y) & 0 = 0, y ^ 0 = y

3.取模(x + y) mod n

1
2
3
4
r = (x + y) % n;

z = x + y;
r = (z < n) ? z : z-n;
1
2
z = x + y;
r = z - (n & -(z >= n)); //这里用到了上面取较小值类似的思路

4.找到二进制中最后一个1

1
r = x & (-x);
x 0010000001010000
-x 1101111110110000
x & (-x) 0000000000010000

5.获取二进制中最后一个1的位置

可以从右向左看最后一位是不是1，不是就右移一位

1
2
3
4
5
6
7
8
9
10
11
12
13
int indexOfLastOne(int x)
{
    int index = 0;
    while (x != 0)
    {
        if (x & 1 == 1)
        {
            return index;
        }
        x = x >> 1;
        ++index;
    }
}
  1. 比n大的最小2次幂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static int nextPowerOf2(int n)
{
    int count = 0;

    // First n in the below  
    // condition is for the  
    // case where n is 0
    if (n > 0 && (n & (n - 1)) == 0)
        return n;

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

    return 1 << count;
}
  1. 比n小的最大2次幂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
static int highestPowerof2SmallerThanN(int n)
{
    int res = 0;
    for (int i = n; i >= 1; i--)
    {
        // If i is a power of 2
        if ((i & (i - 1)) == 0)
        {
            res = i;
            break;
        }
    }
    return res;
}

或者直接logn/log2 取整

1
2
3
4
5
6
static int highestPowerof2(int n)
{

    int p = (int)(Math.log(n) / Math.log(2));
    return (int)Math.pow(2, p);  
}

Reference

  1. Lec 2 | MIT 6.172 Performance Engineering of Software Systems, Fall 2010 (Video)

  2. Lec 2 | MIT 6.172 Performance Engineering of Software Systems, Fall 2010 (PPT)

  3. Bit Twiddling Hacks