< back

Bit Tricks

Number of runs of 1s in a binary number

This was an interesting point found in the Roaring Bitmap paper that shows how to compute the number of runs of 1 values in a binary number.

Taking the original number, you can left-shift it by 1, and then calulcate the 2nd value by bitwise 'and not'ing the result against the original value. This will set a 1 bit for each run that existed. Then you can calculate the Hamming Weight of the result. On most CPUs this will be a single POPCNT (pop count) instruction.

Example

let a = 0b000111000111000111000011     | 0b000111000111000111000011
let b = a << 1                         | 0b001110001110001110000110
let c = b & !a                         | 0b001000001000001000000100
let d = popcnt(c)                      | 4