Bit manipulation¶
Binary number¶
A binary number is a number expressed in the base-2 numeral system or binary numeral system, it is a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" (one).
We say that a certain bit is set, if it is one, and cleared if it is zero.
The binary number
For instance the binary number
Computers represent integers as binary numbers. Positive integers (both signed and unsigned) are just represented with their binary digits, and negative signed numbers (which can be positive and negative) are usually represented with the Two's complement.
unsigned int unsigned_number = 13;
assert(unsigned_number == 0b1101);
int positive_signed_number = 13;
assert(positive_signed_number == 0b1101);
int negative_signed_number = -13;
assert(negative_signed_number == 0b1111'1111'1111'1111'1111'1111'1111'0011);
CPUs are very fast manipulating those bits with specific operations. For some problems we can take these binary number representations to our advantage, and speed up the execution time. And for some problems (typically in combinatorics or dynamic programming) where we want to track which objects we already picked from a given set of objects, we can just use an large enough integer where each digit represents an object and depending on if we pick or drop the object we set or clear the digit.
Bit operators¶
All those introduced operators are instant (same speed as an addition) on a CPU for fixed-length integers.
Bitwise operators¶
Examples:
n = 01011000
n-1 = 01010111
--------------------
n & (n-1) = 01010000
n = 01011000
n-1 = 01010111
--------------------
n | (n-1) = 01011111
n = 01011000
n-1 = 01010111
--------------------
n ^ (n-1) = 00001111
n = 01011000
--------------------
~n = 10100111
Shift operators¶
There are two operators for shifting bits.
-
E.g.
-
E.g.
Notice however that for a fixed-length integer that means dropping the most left digits, and if you shift too much you end up with the number
Useful tricks¶
Set/flip/clear a bit¶
Using bitwise shifts and some basic bitwise operations we can easily set, flip or clear a bit.
Check if a bit is set¶
The value of the
bool is_set(unsigned int number, int x) {
return (number >> x) & 1;
}
Check if the number is divisible by a power of 2¶
Using the and operation, we can check if a number
bool isDivisibleByPowerOf2(int n, int k) {
int powerOf2 = 1 << k;
return (n & (powerOf2 - 1)) == 0;
}
We can calculate
Check if an integer is a power of 2¶
A power of two is a number that has only a single bit in it (e.g.
bool isPowerOfTwo(unsigned int n) {
return n && !(n & (n - 1));
}
Clear the right-most set bit¶
The expression
For example, consider the number
n = 00110100
n-1 = 00110011
--------------------
n & (n-1) = 00110000
Brian Kernighan's algorithm¶
We can count the number of bits set with the above expression.
The idea is to consider only the set bits of an integer by turning off its rightmost set bit (after counting it), so the next iteration of the loop considers the Next Rightmost bit.
int countSetBits(int n)
{
int count = 0;
while (n)
{
n = n & (n - 1);
count++;
}
return count;
}
Count set bits upto ¶
To count the number of set bits of all numbers upto the number
We can use the fact that for numbers upto
0 -> 0 0 0 0
1 -> 0 0 0 1
2 -> 0 0 1 0
3 -> 0 0 1 1
4 -> 0 1 0 0
5 -> 0 1 0 1
6 -> 0 1 1 0
7 -> 0 1 1 1
8 -> 1 0 0 0
We can see that the all the columns except the leftmost have
With the new knowledge in hand we can come up with the following algorithm:
- Find the highest power of
- Calculate the number of set bits from
- Count the no. of set bits in the most significant bit from
- Subtract
int countSetBits(int n) {
int count = 0;
while (n > 0) {
int x = std::bit_width(n) - 1;
count += x << (x - 1);
n -= 1 << x;
count += n + 1;
}
return count;
}
Additional tricks¶
Many more can be found in the book Hacker's Delight.
Language and compiler support¶
C++ supports some of those operations since C++20 via the bit standard library:
has_single_bit
: checks if the number is a power of twobit_ceil
/bit_floor
: round up/down to the next power of tworotl
/rotr
: rotate the bits in the numbercountl_zero
/countr_zero
/countl_one
/countr_one
: count the leading/trailing zeros/onespopcount
: count the number of set bits
Additionally, there are also predefined functions in some compilers that help working with bits. E.g. GCC defines a list at Built-in Functions Provided by GCC that also work in older versions of C++:
__builtin_popcount(unsigned int)
returns the number of set bits (__builtin_popcount(0b0001'0010'1100) == 4
)__builtin_ffs(int)
finds the index of the first (most right) set bit (__builtin_ffs(0b0001'0010'1100) == 3
)__builtin_clz(unsigned int)
the count of leading zeros (__builtin_clz(0b0001'0010'1100) == 23
)__builtin_ctz(unsigned int)
the count of trailing zeros (__builtin_ctz(0b0001'0010'1100) == 2
)__builtin_parity(x)
the parity (even or odd) of the number of ones in the bit representation
Note that some of the operations (both the C++20 functions and the Compiler Built-in ones) might be quite slow in GCC if you don't enable a specific compiler target with #pragma GCC target("popcnt")
.