**Bit manipulation** is the act of algorithmically manipulating bits or other pieces of data shorter than a word. Computer programming tasks that require bit manipulation include low-level device control, error detection and correction algorithms, data compression, encryption algorithms, and optimization. For most other tasks, modern programming languages allow the programmer to work directly with abstractions instead of bits that represent those abstractions. Source code that does bit manipulation makes use of the bitwise operations: AND, OR, XOR, NOT, and possibly other operations analogous to the boolean operators; there are also bit shifts and operations to count ones and zeros, find high and low one or zero, set, reset and test bits, extract and insert fields, mask and zero fields, gather and scatter bits to and from specified bit positions or fields. Integer arithmetic operators can also effect bit-operations in conjunction with the other operators.

## Remove rightmost set bit

**C-style bit-manipulation**

0 1 2 3 4 5 6 7 8 |
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
`n`

is zero, we have`0 & 0xFF..FF`

which is zero - else
`n`

can be written`0bxxxxxx10..00`

and`n - 1`

is`0bxxxxxx011..11`

, so`n & (n - 1)`

is`0bxxxxxx000..00`

.

## Set all bits

**C-style bit-manipulation**

0 1 2 |
x = -1; // -1 == 1111 1111 ... 1111b |

(See here for an explanation of why this works and is actually the best approach.)

**Using std::bitset**

0 1 2 3 |
std::bitset<10> x; x.set(); // Sets all bits to '1' |

## Toggling a bit

**C-style bit-manipulation**

A bit can be toggled using the XOR operator (^).

0 1 2 3 |
// Bit x will be the opposite value of what it is currently number ^= 1LL << x; |

**Using std::bitset**

0 1 2 3 4 5 |
std::bitset<4> num(std::string("0100")); num.flip(2); // num is now 0000 num.flip(0); // num is now 0001 num.flip(); // num is now 1110 (flips all bits) |

## Checking a bit

**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:

0 1 2 |
(number >> x) & 1LL; // 1 if the 'x'th bit of 'number' is set, 0 otherwise |

The right-shift operation may be implemented as either an arithmetic (signed) shift or a logical (unsigned) shift. If number in the expression number `>> x`

has a signed type and a negative value, the resulting value is implementation-deﬁned.

If we need the value of that bit directly in-place, we could instead left shift the mask:

0 1 2 |
(number & (1LL << x)); // (1 << x) if the 'x'th bit of 'number' is set, 0 otherwise |

Either can be used as a conditional, since all non-zero values are considered true.

**Using std::bitset**

0 1 2 3 |
std::bitset<4> num(std::string("0010")); bool bit_val = num.test(1); // bit_val value is set to true; |

## Counting bits set

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:

0 1 2 3 4 5 |
unsigned value = 1234; unsigned bits = 0; // accumulates the total number of bits set in `n` for (bits = 0; value; value >>= 1) bits += value & 1; |

A nice trick (based on Remove rightmost set bit ) is:

0 1 2 3 4 |
unsigned bits = 0; // accumulates the total number of bits set in `n` for (; value; ++bits) value &= value - 1; |

It goes through as many iterations as there are set bits, so it’s good when value is expected to have few nonzero bits.

The method was ﬁrst proposed by Peter Wegner (in CACM 3 / 322 – 1960) and it’s well known since it appears in C Programming Language by Brian W. Kernighan and Dennis M. Ritchie.

This requires 12 arithmetic operations, one of which is a multication:

0 1 2 3 4 5 6 7 8 9 10 |
unsigned popcount(std::uint64_t x) { const std::uint64_t m1 = 0x5555555555555555; // binary: 0101... const std::uint64_t m2 = 0x3333333333333333; // binary: 00110011.. const std::uint64_t m4 = 0x0f0f0f0f0f0f0f0f; // binary: 0000111100001111 x -= (x >> 1) & m1; // put count of each 2 bits into those 2 bits x = (x & m2) + ((x >> 2) & m2); // put count of each 4 bits into those 4 bits x = (x + (x >> 4)) & m4; // put count of each 8 bits into those 8 bits return (x * h01) >> 56; // left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... } |

This kind of implementation has the best worst-case behavior (see Hamming weight for further details).

Many CPUs have a speciﬁc instruction (like x86’s popcnt) and the compiler could oﬀer a speciﬁc (**non standard**) built in function. E.g. with g++ there is:

0 1 2 |
int __builtin_popcount (unsigned x); |

## Check if an integer is a power of 2

The `n & (n - 1)`

trick (see Remove rightmost set bit) is also useful to determine if an integer is a power of 2:

0 1 2 |
bool power_of_2 = n && !(n & (n - 1)); |

Note that without the ﬁrst part of the check (`n &&`

), `0`

is incorrectly considered a power of 2.

## Setting a bit

**C-style bit manipulation**

A bit can be set using the bitwise OR operator (`|`

).

0 1 2 3 |
// Bit x will be set number |= 1LL << x; |

**Using std::bitset**

`set(x)`

or `set(x,true)`

– sets bit at position `x`

to `1`

.

0 1 2 3 4 5 |
std::bitset<5> num(std::string("01100")); num.set(0); // num is now 01101 num.set(2); // num is still 01101 num.set(4,true); // num is now 11110 |

## Clearing a bit

**C-style bit-manipulation**

A bit can be cleared using the bitwise AND operator (`&`

).

0 1 2 3 |
// Bit x will be cleared number &= ~(1LL << x); |

**Using std::bitset**

`reset(x)`

or `set(x,false)`

– clears the bit at position `x`

.

0 1 2 3 4 5 |
std::bitset<5> num(std::string("01100")); num.reset(2); // num is now 01000 num.reset(0); // num is still 01000 num.set(3,false); // num is now 00000 |

## Changing the nth bit to x

**C-style bit-manipulation**

0 1 2 3 |
// 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.

0 1 2 3 4 |
std::bitset<5> num(std::string("00100")); num.set(0,true); // num is now 00101 num.set(2,false); // num is now 00001 |

## Bit Manipulation Application: Small to Capital Letter

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 diﬀer solely in the bit in parenthesis. In this case, converting the a letter from small to capital is basically setting the bit in parenthesis to one. To do so, we do the following:

0 1 2 3 4 5 6 7 8 9 |
/**************************************** convert small letter to captial letter. ======================================== a: 01100001 mask: 11011111 <-- (0xDF) 11(0)11111 :--------- a&mask: 01000001 <-- A letter *****************************************/ |

The code for converting `a`

letter to `A`

letter is

0 1 2 3 4 5 6 7 8 9 10 11 |
#include <cstdio> int main() { char op1 = 'a'; // "a" letter (i.e. small case) int mask = 0xDF; // choosing a proper mask printf("a (AND) mask = A\n"); printf("%c & 0xDF = %c\n", op1, op1 & mask); return 0; } |

The result is

0 1 2 3 4 5 |
$ g++ main.cpp -o test1 $ ./test1 a (AND) mask = A a & 0xDF = A |