引言
为什么要学bithack？这个视频或许能给出答案
那么先简单总结一下这个视频中的技巧
代码尚未测试
const NEWTON_ITER: usize = 1;
fn inverse_sqrt(mut num: f64) -> f64{
//edge cases
if !num.is_sign_positive() || num.is_nan(){ return f64::NAN; }
if num.is_subnormal(){ return f64::INFINITY; }
if num.is_infinity(){ return 0.0 }
let tmp: f64 = num * 0.5;
//cast binary representation of f64
let mut x = num.to_bits();
//the magic happens
x = 0x5f3759df - (x >> 1);
//cast back
num = f64::from_bits(x);
//Newton's approximation
for _ in 0..NEWTON_ITER{ num = num * ( 1.5 - (tmp * num * num) ); }
num
}
笔记
基础 - 改变指定位置的值
x = (1<<k) | x; //将kth bit设定为1
x = ~(1<<k) & x; //将kth bit设定为0
x = (1<<k) ^ x; //将kth bit翻转
Trailing Zeros -> Ones
x = x | (x-1); //将trailing zero全变成1 x = x & (x-1); //将最后一个1改成0 x = x & -x; //只保留最后一个1
2s compliment
//下面式子中x始终为正 -x = (~x) + 1; //正->负 x = ~((-x)-1); //负->正
Masks
x = a & mask; //只拷贝mask下的内容 y = a & ~mask; //只拷贝不在mask下的内容 z = x | y; //两个在一起可以完美组合成新的值
Swapping bits
p = (x >> a) ^ (x >> b) & 1; //判断a bit与b bit是否相同，若不同，则p = 0
x ^= (p << a);
x ^= (p << b);
Kernighan’s Population Count
每次都使用 x = x & (x-1), 直到x = 0
这种方法速度很慢，如果需要population count, rust中有u32::count_ones()
使用的是CPU指令集内置的功能
Leetcode-191
我此题的题解
Counting bit islands
(x&1) + ( x.count_ones(x ^ (x >> 1)) /2 )
x & 1可以理解为将x右移的最后一位转回到最高位，然后进行异或计算
Bit Scan Forwards(BSF)
fn bsf(mut x: u32) -> usize{
if x == 0 {return 0;}
x = x & -x; //只保留最后一个1
((x & 0xffff0000) != 0) as usize * 16
+ ((x & 0xff00ff00) != 0) as usize * 8
+ ((x & 0xf0f0f0f0) != 0) as usize * 4
+ ((x & 0xcccccccc) != 0) as usize * 2
+ ((x & 0xaaaaaaaa) != 0) as usize
}
这个可能跟Population count 一样不是最优解法，rust中有u32::trailing_zeros() 和 u32::trailing_ones()
Next Lexicographic Permutation
Given a bit string, generate the next permutation above with the same number of 1s