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.
It's clearly $$$O(2^n)$$$. $$$O(3^n)$$$ is for enumerating all masks and their submasks.
You're right. Thank you. Gonna edit
What does "next permutation" mean?
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$$$.
Doesn't work for
x = 0:)Iterating over all bits set to
1:If
maskislong long, you need to replaceintbylong long(obviously) and__builtin_ctzby__builtin_ctzll. Probably C++20 has a method likectzor something for thisAlso its dual (for supermask enumeration), just for the sake of completeness. Here $$$n$$$ is the number of bits.
what is a supermask?
My code does not do submask enumeration, it does another thing
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
~maskinstead):Note that this gives the locations of the zeros before the position $$$n$$$ (zero-indexed from the right), and needs
maskto be less than $$$2^n$$$.Zwerr