Kerekiw's blog

Essential bitwise hacks and twiddlings
By Kerekiw, 3 years ago, In English

Formulas are given in C/C++, which uses two's complemet

Beginner level

x = (1 << y) ^ x — toggle a bit.

x = (1 << y) | x — addding a bit.

x = ~(1 << y) & x — removing a bit.

if (1 << y & x) — check whether y-th bit is set.

Intermediate level

-x = ~x + 1 — negative $$$ x $$$ in two's complement representation.

x & (-x) — least significant bit, LSB

if (x && !((x-1) & x) — check whether x is a power of two

Complex level

Bit swap

p = ((x >> a) ^ (x >> b)) & 1
x ^= (p << a)
x ^= (p << b)

Number of set bits

aka population count. x = x & (x-1) removes least significant bit, Brian Kernighan method.

for (c = 0; x; c++)
    x = x & (x-1)

Swapping values

b ^= a ^= b;
a ^= b;

All submasks of mask

Excluding blank mask. Also, enumerating all masks and their submasks is $$$ O(3^n) $$$.

for (int s = m; s; s = (s-1)&m)
	//do something

Bit scan forward

BSF, null indexed position of LSB. $$$ x $$$ should not be zero.

x = x & (-x);
int pos = 0;
if (x & 0xffff0000) pos += 16;
if (x & 0xff00ff00) pos += 8;
if (x & 0xf0f0f0f0) pos += 4;
if (x & 0xcccccccc) pos += 2;
if (x & 0xaaaaaaaa) pos += 1;

Next permutation

Rearranges bit set of number into the lexicographically next greater permutation.

t = x | (x - 1);
x = (t + 1) | (((~t & -~t) - 1) >> (BSF(v) + 1));

Summary

Most of these are useless or can be replaced with builtin functions, but if some of you find them intersting you should check out this list or this video.

  • Vote: I like it
  • +35
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Excluding blank mask, $$$O(3^n)$$$.

It's clearly $$$O(2^n)$$$. $$$O(3^n)$$$ is for enumerating all masks and their submasks.

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

What does "next permutation" mean?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Permutes bit set of $$$ x $$$ to lexicographicaly next permutation, assuming they are sorted in ascending order, e.g. $$$ 100101 $$$ will be permuted to $$$ 100110 $$$, $$$ 100110 $$$ will be permuted to $$$ 101001$$$.

    → Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it 
(x&(x-1)) ---> Checking The Power of Two.   :)
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Doesn't work for x = 0 :)

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Iterating over all bits set to 1:

for (int m = mask; m; m &= m - 1) {
    do_something(__builtin_ctz(m));
}

If mask is long long, you need to replace int by long long (obviously) and __builtin_ctz by __builtin_ctzll. Probably C++20 has a method like ctz or something for this

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Also its dual (for supermask enumeration), just for the sake of completeness. Here $$$n$$$ is the number of bits.

    for (int m = mask; m < (1 << n); m = (m + 1) | mask) {
    // m is a supermask of m
}
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what is a supermask?

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      My code does not do submask enumeration, it does another thing

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        Ah yes, I somewhat misread the update condition (for submask enumeration it's m = (m - 1) & mask).

        On another note, you can iterate over the zeros in the mask by using the following (very similar) loop (though it is equivalent to doing the same thing as you mentioned with ~mask instead):

        for (int m = mask; m < (1 << n) - 1; m |= (m + 1)) {
    // do something with __builtin_ctz(m + 1)
}

        Note that this gives the locations of the zeros before the position $$$n$$$ (zero-indexed from the right), and needs mask to be less than $$$2^n$$$.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Zwerr

→ Reply