Tutorial by Examples

C-style bit manipulation A bit can be set using the bitwise OR operator (|). // Bit x will be set number |= 1LL << x; Using std::bitset set(x) or set(x,true) - sets bit at position x to 1. std::bitset<5> num(std::string("01100")); num.set(0); // num is now 01101 ...

C-style bit-manipulation A bit can be cleared using the bitwise AND operator (&). // Bit x will be cleared number &= ~(1LL << x); Using std::bitset reset(x) or set(x,false) - clears the bit at position x. std::bitset<5> num(std::string("01100")); num.reset(2); ...

C-style bit-manipulation A bit can be toggled using the XOR operator (^). // Bit x will be the opposite value of what it is currently number ^= 1LL << x; Using std::bitset std::bitset<4> num(std::string("0100")); num.flip(2); // num is now 0000 num.flip(0); // num is n...

C-style bit-manipulation The value of the bit can be obtained by shifting the number to the right x times and then performing bitwise AND (&) on it: (number >> x) & 1LL; // 1 if the 'x'th bit of 'number' is set, 0 otherwise The right-shift operation may be implemented as either a...

C-style bit-manipulation // Bit n will be set if x is 1 and cleared if x is 0. number ^= (-x ^ number) & (1LL << n); Using std::bitset set(n,val) - sets bit n to the value val. std::bitset<5> num(std::string("00100")); num.set(0,true); // num is now 00101 num.set(...

C-style bit-manipulation x = -1; // -1 == 1111 1111 ... 1111b (See here for an explanation of why this works and is actually the best approach.) Using std::bitset std::bitset<10> x; x.set(); // Sets all bits to '1'

C-style bit-manipulation template <typename T> T rightmostSetBitRemoved(T n) { // static_assert(std::is_integral<T>::value && !std::is_signed<T>::value, "type should be unsigned"); // For c++11 and later return n & (n - 1); } Explanation if...

The population count of a bitstring is often needed in cryptography and other applications and the problem has been widely studied. The naive way requires one iteration per bit: unsigned value = 1234; unsigned bits = 0; // accumulates the total number of bits set in `n` for (bits = 0; value; ...

The n & (n - 1) trick (see Remove rightmost set bit) is also useful to determine if an integer is a power of 2: bool power_of_2 = n && !(n & (n - 1)); Note that without the first part of the check (n &&), 0 is incorrectly considered a power of 2.

One of several applications of bit manipulation is converting a letter from small to capital or vice versa by choosing a mask and a proper bit operation. For example, the a letter has this binary representation 01(1)00001 while its capital counterpart has 01(0)00001. They differ solely in the bit in...