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

c++

  1. split
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static void _split(const string &s, char delim,
                   vector<string> &elems) {
    stringstream ss(s);
    string item;

    while (getline(ss, item, delim)) {
        elems.push_back(item);
    }
}

vector<string> split(const string &s, char delim) {
    vector<string> elems;
    _split(s, delim, elems);
    return elems;
}

sql

1. 把每一行的’m’ ‘f’互换

1
update salary set sex = IF (sex = 'm', 'f', 'm')
1
2
3
4
5
update salary
set sex = (case
when sex = 'm' then 'f'
ELSE 'm'
end)

LeetCode在sql语句上的执行时间真是玄学，一段一样的sql语句执行时间差几百ms

1
2
3
4
5
6
| id | name | sex | salary |
|----|------|-----|--------|
| 1  | A    | m   | 2500   |
| 2  | B    | f   | 1500   |
| 3  | C    | m   | 5500   |
| 4  | D    | f   | 500    |

2. MySQL LIMIT

1
2
3
4
select * from table limit offset,count

select * from table1 limit 2 #从第一行开始开始取两行
select * from table1 limit 0,2 #从第一行开始开始取两行