Collection of Bithack Tricks

Introduction

Why learn bithack? Perhaps this video can provide an answer

And over the weekend, explaining data types to classmates in the math department made me realize that understanding the representation of different data types in memory is an important step between “knowing Python” and “understanding programming”. Of course, in the end, you will find that the essence of writing code is ultimately math - calculus, linear algebra, discrete math, and Boolean Algebra.

Let’s briefly summarize the tricks in this video first.

Code not yet tested

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
}

Notes

Basics - Changing the value at a specified position

x = (1<<k) |  x; // set kth bit to 1
x = ~(1<<k) & x; // set kth bit to 0
x = (1<<k) ^ x; // flip kth bit

Trailing Zeros -> Ones

x = x | (x-1); // turn trailing zeros into ones x = x & (x-1); // change the last 1 to 0 x = x & -x; // keep only the last 1

2s compliment

//x is always positive in the following expressions -x = (~x) + 1; //positive -> negative x = ~((-x)-1); //negative -> positive

Masks

x = a & mask; // copy only the content under mask y = a & ~mask; // copy only the content not under mask z = x | y; // two combined perfectly into a new value

Swapping bits

p = (x >> a) ^ (x >> b) & 1; // check if a bit and b bit are the same, if not, p = 0
x ^= (p << a);
x ^= (p << b);

Kernighan’s Population Count

Always use x = x & (x-1) until x = 0 This method is slow. If a population count is needed, Rust has u32::count_ones() which uses built-in CPU instructions Leetcode-191 My solution to this problem

Counting bit islands

(x&1) + ( x.count_ones(x ^ (x >> 1)) /2 ) x & 1 can be understood as moving the last bit of x to the highest position, and then performing XOR calculation

Bit Scan Forwards(BSF)

fn bsf(mut x: u32) -> usize{
    if x == 0 {return 0;}
    x = x & -x; // keep only the last 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
}

This may not be the optimal solution, similar to Population count. Rust has u32::trailing_zeros() and u32::trailing_ones()

Next Lexicographic Permutation

Given a bit string, generate the next permutation above with the same number of 1s