🐂🍺位运算技巧一览表
维护者 - Keon Kim 欢迎pull requests
设置第n位（置为1）
x | (1<<n)
取消第n位（置为0）
x & ~(1<<n)
切换第n位
x ^ (1<<n)
向上取整至2的幂
unsigned int v; //only works if v is 32 bit
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
向下取整
n >> 0
5.7812 >> 0 // 5
取最大int值
int maxInt = ~(1 << 31);
int maxInt = (1 << 31) - 1;
int maxInt = (1 << -1) - 1;
int maxInt = -1u >> 1;
取最小int值
int minInt = 1 << 31;
int minInt = 1 << -1;
取最大long值
long maxLong = ((long)1 << 127) - 1;
乘以2
n << 1; // n*2
除以2
n >> 1; // n/2
乘以2的m次幂
n << m;
除以2的m次幂
n >> m;
检查相等
在Javascript中快35%
(a^b) == 0; // a == b
!(a^b) // use in an if
检查奇数
(n & 1) == 1;
交换两个值
//version 1
a ^= b;
b ^= a;
a ^= b;
//version 2
a = a ^ b ^ (b = a)
取绝对值
//version 1
x < 0 ? -x : x;
//version 2
(x ^ (x >> 31)) - (x >> 31);
取二者最大值
b & ((a-b) >> 31) | a & (~(a-b) >> 31);
取二者最小值
a & ((a-b) >> 31) | b & (~(a-b) >> 31);
检查符号一致性
(x ^ y) >= 0;
符号取反
i = ~i + 1; // or
i = (i ^ -1) + 1; // i = -i
计算2n
1 << n;
是否为2的幂
n > 0 && (n & (n - 1)) == 0;
m对2n取模
m & ((1 << n) - 1);
取平均值
(x + y) >> 1;
((x ^ y) >> 1) + (x & y);
取n的第m位（由低到高）
(n >> (m-1)) & 1;
置n的第m位为0（由低到高）
n & ~(1 << (m-1));
检查第n位是否为1
if (x & (1<<n)) {
n-th bit is set
} else {
n-th bit is not set
}
分离（提取）右起第一个为1的位
x & (-x)
分离（提取）右起第一个为0的位
~x & (x+1)
置右起第一个0位为1
x | (x+1)
置右起第一个1位为0
x & (x-1)
n + 1
-~n
n - 1
~-n
符号取反
~n + 1;
(n ^ -1) + 1;
if (x == a) x = b; if (x == b) x = a;
x = a ^ b ^ x;
交换相邻位
((n & 10101010) >> 1) | ((n & 01010101) << 1)
m与n最右侧的相反位
(n^m)&-(n^m) // returns 2^x where x is the position of the different bit (0 based)
m与n最右侧的相同位
~(n^m)&(n^m)+1 // returns 2^x where x is the position of the common bit (0 based)
这些是受fast inverse square root method启发而来的技巧。 大部分为原创。
float转换为bit数组(unsigned uint32_t)
#include <stdint.h>
typedef union {float flt; uint32_t bits} lens_t;
uint32_t f2i(float x) {
return ((lens_t) {.flt = x}).bits;
}注：使用union进行转换在C++中是未定义行为，改使用std::memcpy。
将bit数组转换回float
float i2f(uint32_t x) {
return ((lens_t) {.bits = x}).flt;
}利用frexp从正浮点数中近似取出bit数组
frexp将数值按照2n进行分解，即man, exp = frexp(x)表示man * 2exp = x同时0.5 <= man < 1.
man, exp = frexp(x);
return (uint32_t)((2 * man + exp + 125) * 0x800000);注：此操作最大产生2-16相对误差，由于man + 125覆盖了最后8位，保留了尾数的前16位。
快速计算平方根倒数
return i2f(0x5f3759df - f2i(x) / 2);注：此处使用了i2f与f2i函数。
借助无穷级数快速计算正数的n次方根
float root(float x, int n) {
#DEFINE MAN_MASK 0x7fffff
#DEFINE EXP_MASK 0x7f800000
#DEFINE EXP_BIAS 0x3f800000
uint32_t bits = f2i(x);
uint32_t man = bits & MAN_MASK;
uint32_t exp = (bits & EXP_MASK) - EXP_BIAS;
return i2f((man + man / n) | ((EXP_BIAS + exp / n) & EXP_MASK));
}推导见此处。
Fast Arbitrary Power
return i2f((1 - exp) * (0x3f800000 - 0x5c416) + f2i(x) * exp)注：0x5c416是此方法所给出的偏置值。若带入exp = -0.5，则为快速平方根倒数方法中的常量0x5f3759df。
此方法推导见these set of slides。
快速几何平均
几何平均数是n个数连乘积的n次方根
#include <stddef.h>
float geometric_mean(float* list, size_t length) {
// Effectively, find the average of map(f2i, list)
uint32_t accumulator = 0;
for (size_t i = 0; i < length; i++) {
accumulator += f2i(list[i]);
}
return i2f(accumulator / n);
}推导见此处。
快速自然对数
#DEFINE EPSILON 1.1920928955078125e-07
#DEFINE LOG2 0.6931471805599453
return (f2i(x) - (0x3f800000 - 0x66774)) * EPSILON * LOG2注：此方法使用0x66774作为偏置值。末尾乘以ln(2)是因为此方法其余部分计算的为log2(x)。
推导见此处。
快速自然指数
return i2f(0x3f800000 + (uint32_t)(x * (0x800000 + 0x38aa22)))注：偏置值0x38aa22对应为基数的乘法系数。特别地，它对应着2z = e中的z
推导见此处。
转换字母为小写
按位或空格字符 => (x | ' ')
结果恒为小写字母，即使原字符已为小写
例如：('a' | ' ') => 'a' ; ('A' | ' ') => 'a'
转换字母为大写
按位与下划线字符 => (x & '_')
结果恒为大写字母，即使原字符已为大写
例如：('a' & '_') => 'A' ; ('A' & '_') => 'A'
字母大小写互换
按位异或空格字符 => (x ^ ' ')
例如：('a' ^ ' ') => 'A' ; ('A' ^ ' ') => 'a'
字母表序号
按位与chr(31)/binary('11111')/(hex('1F') => (x & "\x1F")
结果在1~26之间，大小写无关
例如：('a' & "\x1F") => 1 ; ('B' & "\x1F") => 2
字母表序号（仅大写）
按位与问号字符 => (x & '?') 或按位异或@字符 => (x ^ '@')
例如：('C' & '?') => 3 ; ('Z' ^ '@') => 26
字母表序号（仅小写）
按位异或反引号字符/chr(96)/binary('1100000')/hex('60') => (x ^ '`')
例如：('d' ^ '`') => 4 ; ('x' ^ '`') => 24
使用位移运算快速转换R5G5B5颜色格式至R8G8B8
R8 = (R5 << 3) | (R5 >> 2)
G8 = (R5 << 3) | (R5 >> 2)
B8 = (R5 << 3) | (R5 >> 2)
注：使用任何非英文字符会产生错误结果