二进制技巧

二进制位运算的技巧特别多，这里就做一份cheat sheet，希望能帮助到大家。不过过于简单的就不列举了

单行表达式

多行的技巧

1. 两数交换不使用第三个变量

void swap(int* a, int* b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

2. 奇偶校验码

int check_bit(int n)
{
    n ^= n >> 1;
    n ^= n >> 2;
    n ^= n >> 4;
    n ^= n >> 8;
    n ^= n >> 16;
    return n & 1;
}

3. 计算二进制中的1的个数(popcount)

uint32_t method_1_uint32_popcount(uint32_t n)
{
	n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
	n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
	n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
	n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
	n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
	return n;
}

uint32_t method_2_uint32_popcount(uint32_t n)
{
	n = n - ((n >> 1) & 0x55555555);
	n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
	n = (n + (n >> 4)) & 0x0f0f0f0f;
	n = n + (n >> 8);
	n = n + (n >> 16);
	return n & 0x3f;
}

uint32_t method_3_uint32_popcount(uint32_t n)
{
	n = n - ((n>>1) & 0x55555555);
	n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
	return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

4. 计算下一组合

前提：我们使用一个整数的二进制位来代表对应集合上的元素有没有选中，从而来表达一个组合。当我们要遍历所有组合的时候，就可以用这个办法了

int next_combination(int k)
{
    int b = k & -k, t = (k + b);
    return (((t ^ k) >> 2) / b) | t;
}

5. n皇后问题位运算实现

uint64_t queen(uint32_t row, uint32_t lb, uint32_t rb)
{
    if (row == 0)
        return 1;
    uint64_t sum = 0;
    for (uint32_t r = row; r; r &= r - 1)
    {
        uint32_t p = r ^ (r & (r - 1));
        if ((p & lb) == 0 && (p & rb) == 0)
            sum += queen(row ^ p, (lb | p) << 1, (rb | p) >> 1);
    }
    return sum;
}

uint64_t nqueen(int n) // 返回值为棋盘大小n时解的个数
{
    return queen(((uint32_t)1 << n) - 1, 0, 0);
}

6. 古老的快速平方根倒数

求 1/sqrt(n)，这段代码出自Quake-III Arena (雷神之锤3)源代码 /game/code/q_math.c，针对 IEEE 754 标准的单精度浮点格式

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

#ifndef Q3_VM
#ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
	return y;
}

注：使用常数 0x5f375a86 可以使得结果误差更小，详见维基百科

7. 绘画Sierpinski三角

#include <stdio.h>
int main(void)
{
    const int n = (1 << 5);
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j <= i; ++j)
           putchar( ( i & j ) == j ? '#' : ' ');
        printf("\n");
    }
    return 0;
}

输出结果

#
##
# #
####
#   #
##  ##
# # # #
########
#       #
##      ##
# #     # #
####    ####
#   #   #   #
##  ##  ##  ##
# # # # # # # #
################
#               #
##              ##
# #             # #
####            ####
#   #           #   #
##  ##          ##  ##
# # # #         # # # #
########        ########
#       #       #       #
##      ##      ##      ##
# #     # #     # #     # #
####    ####    ####    ####
#   #   #   #   #   #   #   #
##  ##  ##  ##  ##  ##  ##  ##
# # # # # # # # # # # # # # # #
################################