Bits and C++

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:

Third-party solutions

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 - space-optimized container specialization which doesn't store values in separate addresses, so it doesn't work as other STL containers

Flaws:

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 - variable-size container, where each element is stored in it's own address

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

Bit tricks

Other resources

Share

follow