Computers store information using bits. Bit is a smallest portion of information - it can have only value 0 or 1. Bit manipulation operations are useful at lowest level of programming - when you operate on hardware device level. They can be also useful for algorithm optimizations since bit is the smallest portion of data.

## Build-in operators

Bit shift operators "<<" (shift left) and ">>" (shift right) can be used to shift value's bits.

For example you can:

```
unsigned a = 120; // binary 01111000
unsigned b = a >> 2; // binary 00011110
unsigned c = a << 1; // binary 11110000
```

AND operator "&" can be used to switch-off part of bits in value, example:

```
unsigned a = 120; // binary 01111000
unsigned b = 30; // binary 00011110
// bitwise AND operator ('&'): only bits that are = '1' in both arguments are also = '1' in result
unsigned c = a & b; // binary 00011000
```

OR operator "|" can be used to calculate which bits are = '1' in any of it's arguments

```
unsigned a = 120; // binary 01111000
unsigned b = 30; // binary 00011110
unsigned c = a & b; // binary 01111110 = 126
```

XOR operator "^" can be used to reverse some bits in first argument, only bits that are in just one argument = '1' will stay as '1' in result

```
unsigned a = 120; // binary 01111000
unsigned b = 30; // binary 00011110
unsigned c = a ^ b; // binary 01100110 = 102
```

NOT operator "!" changes all bits to negated, so "1" becomes "0" and "0" becomes "1"

```
unsigned a = 120; // binary 01111000
unsigned b = !a; // binary 10000111 = 135
```

See also:

## Binary constants

**C++14 binary literals**
Starting from C++14 you will be able to use build-in support for binary constants as in example:

```
int a = 0b01111000;
```

See:

- Safety in Numbers: Introducing C++14's Binary Literals, Digit Separators, and Variable Templates - Danny Kalev, 2014

**Third-party solutions**

- Macro BOOST_BINARY
- Coding Binary as Binary - Ofek Shilon, 2009 on "binary4" template

## Formatting

You can use the following function to print value as binary number:

```
#include <iostream>
#include <bitset>
using namespace std;
void show_binary(unsigned short int value, unsigned int width)
{
unsigned int t = 1;
if (width > 1)
t = t << (width - 1);
for(; t>0; t = t/2)
if(value & t) cout << '1';
else cout << '0';
}
int main() {
show_binary(12, 16); // shows 0000000000001100
}
```

C++ has also **bitset** type which simplifies work with bits, but requires width to be defined during compilation:

```
#include <iostream>
#include <bitset>
using namespace std;
void show_binary(unsigned short int value) {
bitset<16> bits(value);
cout << bits;
}
int main() {
show_binary(12); // shows 0000000000001100
}
```

## Signed integers

Signed integers allow you to store values which are less than zero. They can be stored as normal unsigned integer and interpreted as signed when required ("2's complement encoding method").

To test this, consider the following code (assuming unsigned short has 16 bits):

```
#include <iostream>
#include <climits>
#include <bitset>
using namespace std;
void show_binary(unsigned short int value) {
bitset<16> bits(value);
cout << bits;
}
// check if value is < 0
bool is_negative_signed_emul(unsigned short int value) {
static const unsigned short int mask = 1 << 15;
return (value & mask);
}
// reverse sign of value in emulated mode
unsigned short int neg_signed_emul(unsigned short int value) {
return (value ^ USHRT_MAX) + 1;
}
// show signed emulated in unsigned
void show_signed_emul(unsigned short int value) {
if (is_negative_signed_emul(value)) {
value = neg_signed_emul(value);
cout << "-";
}
cout << value;
}
int main() {
unsigned short int a = 12; // binary 1100
unsigned short int b;
unsigned short int c;
show_binary(a);
cout << " = " << a << endl;
b = 13;
c = a - b;
show_binary(c);
cout << " = " << c << " = " << a << " - " << b << " = ";
show_signed_emul(c);
cout << endl;
a = c;
b = 2;
c = a - b;
show_binary(c);
cout << " = " << c << " = " << a << " - " << b << " = ";
show_signed_emul(c);
cout << endl;
a = c;
b = 3;
c = a + b;
show_binary(c);
cout << " = " << c << " = " << a << " + " << b << endl;
a = c;
b = 1;
c = a + b;
show_binary(c);
cout << " = " << c << " = " << a << " + " << b << endl;
a = c;
c = neg_signed_emul(a); // change sign
show_binary(c);
cout << " = " << c << " = NEG(" << a << ")" << " = ";
show_signed_emul(c);
cout << endl;
return 0;
}
```

Output:

```
0000000000001100 = 12
1111111111111111 = 65535 = 12 - 13 = -1
1111111111111101 = 65533 = 65535 - 2 = -3
0000000000000000 = 0 = 65533 + 3
0000000000000001 = 1 = 0 + 1
1111111111111111 = 65535 = NEG(1) = -1
```

See:

## Bit containers

There are few containers that can hold bool values. See list below:

1) std::vector

Flaws:

- vector
: More Problems, Better Solutions - Herb Sutter, 1999

2) std::bitset - fixed-size bit container, works like a better "unsigned int", specialized for bit operations, size only limited by available memory

3) boost::container::vector

4) boost::dynamic_bitset - version of std::bitset with size specified in run-time

## Bit counting

- boost::compute::popcount
- in C: Counting bits set, in parallel
- Efficient counting 1s in a binary sequence
- in C: Fast Bit Counting
- popcnt: __popcnt16, __popcnt, __popcnt64 - VS C/C++
- Faster population counts - Andrew Dalke, 2011

## Other bit tricks

- The bit twiddler - Stephan Brumme
- Bit Twiddling Hacks - Sean Eron Anderson

## Other resources

- Bitwise Operators in C and C++: A Tutorial
- The Standard Librarian: Bitsets and Bit Vectors - Matthew H. Austern, 2001