Bogotobogo
contact@bogotobogo.com


Bookmark and Share




C++ Tutorial
Quiz - Bit Manipulation - 2012
cplusplus logo

List of C++ Tutorials


DoSanSuhWon


List of codes

Codes - Bit Manipulation

Byte Prefixes

byte prefixes2




byte prefixes



Bitwise Operations

~ complement Bit n of ~x is the opposite of bit n of x
& Bitwise And Bit n of x&y is 1 if bit n of x and bit n of y is 1.
| Bitwise Or Bit n of x|y is 1 if bit n of x or bit n of y is 1.
^ Bitwise Exclusive Or Bit n of x^y is 1 if bit n of x or bit n of y is 1 but not if both are 1.
>> Right Shift (divide by 2) Bit n of x>>s is bit n-s of x.
<< Left Shift (multiply by 2) Bit n of x<<s is bit n+s of x.


Your Ad Here


bitwise Complement: The bitwise complement operator, the tilde, ~, flips every bit. The tilde is sometimes called a twiddle, and the bitwise complement twiddles every bit:

This turns out to be a great way of finding the largest possible value for an unsigned number (see Two's Complement): 

unsigned int max = ~0;

bitwise AND: The bitwise AND operator is a single ampersand: &: 

01001000 & 
10111000 = 
--------
00001000

bitwise OR: The bitwise OR operator is a |: 

01001000 | 
10111000 = 
--------
11111000

bitwise Exclusive OR (XOR): The exclusive-or operation takes two inputs and returns a 1 if either one or the other of the inputs is a 1, but not if both are. That is, if both inputs are 1 or both inputs are 0, it returns 0. Bitwise exclusive-or, with the operator of a carrot, ^, performs the exclusive-or operation on each pair of bits. Exclusive-or is commonly abbreviated XOR. 

01110010 ^
10101010 
--------
11011000

Suppose, we have some bit, either 1 or 0, that we'll call Z. When we take Z XOR 0, then we always get Z back: if Z is 1, we get 1, and if Z is 0, we get 0. On the other hand, when we take Z XOR 1, we flip Z. If Z is 0, we get 1; if Z is 1, we get 0:

  • myBits ^ 0 : No change
  • myBits ^ 1 : Flip

It's a kind of selective twiddle(~)..
So, if we do XOR against 111...1111, all the bits of myBits flipped. It's equivalent of doing twiddle(~)..

Another interesting trick using the XOR: It does in place swap of integers.
If we apply the XOR operation twice -- say we have a bit, A, and another bit B, and we set C equal to A XOR B, and then take C XOR B: we get A XOR B XOR B, which essentially either flips every bit of A twice, or never flips the bit, so we just get back A. (We can also think of B XOR B as cancelling out.) As an exercise, can we think of a way to use this to exchange two integer variables without a temporary variable?
Check In-Place Integer Swap with Bit Manipulation.


right shift operator (>>): Moving all the bits of a number a specified number of places to the right. Note that a bitwise right-shift will be the equivalent of integer division by 2:

00000101(5)  >>  1
--------
00000010(2)

left shift operator (<<): Moving all the bits of a number a specified number of places to the left: 

[myVariable]<<[number of places]

Suppose we have number 8 written in binary 00001000. If we wanted to shift it to the left 2 places, we'd end up with 00100000; everything is moved to the left two places, and zeros are added as padding. This is the number 32:

00001000(8)  <<  2
--------
00100000(32)

Actually, left shifting is the equivalent of multiplying by a power of two:

x << n
--------
x * (1 << n)

More specifically:

8 << 2
--------
8 * (1 << 2)
--------
32

Set a bit (where n is the bit number, and 0 is the least significant bit):

 unsigned char a |= (1 << n);

Example:

a               1 0 0 0 0 0 0 0
a |= (1 << 1) = 1 0 0 0 0 0 1 0
a |= (1 << 3) = 1 0 0 0 1 0 0 0
a |= (1 << 5) = 1 0 1 0 0 0 0 0

Clear a bit:

 unsigned char b &= ~(1 << n);

Example:

b                1 1 1 1 1 1 1 1
b &= ~(1 << 1) = 1 1 1 1 1 1 0 1
b &= ~(1 << 3) = 1 1 1 1 0 1 1 1
b &= ~(1 << 5) = 1 1 0 1 1 1 1 1

Toggle a bit:

 unsigned char c ^= (1 << n);

Example:

c               1 0 0 1 1 0 1 1
c ^= (1 << 1) = 1 0 0 1 1 0 0 1
c ^= (1 << 3) = 1 0 0 1 0 0 1 1
c ^= (1 << 5) = 1 0 1 1 1 0 1 1

Test a bit: 

 unsigned char e = d & (1 << n); //d has the byte value.


Setting and Clearing a Bit

The code below shows how to set or clear a bit of an integer.

#include <iostream>

using namespace std;

void binary(unsigned int n)
{
	for(int i = 256; i > 0; i = i/2) {
		if(n & i) 
			cout << " 1";
		else
			cout << " 0";
	}
	cout << endl;
}

bool getBit(int n, int index)
{
	return ( (n & (1 << index) ) > 0);
}

int setBit(int n, int index, bool b)
{
	if(b)
		return (n | (1 << index)) ;	
	else {
		int mask = ~(1 << index);
		return n & mask;
	}
}

int main()
{
	int num, index;

	num = 16;

	cout << "Input" << endl;
	for (int i = 7; i >= 0; i--) 
		cout << getBit(num,i) << " ";
	cout << endl;

	/* set bit */
	index = 6;
	cout << "Setting " << index << "-th bit" << endl;
	num = setBit(num, index, true);
	for (int i = 7; i >= 0; i--) 
		cout << getBit(num,i) << " ";
	cout << endl;

	/* unset (clear) bit */
	index = 4;
	cout << "Unsetting (Clearing) " << index << "-th bit" << endl;
	num = setBit(num, index, false);
	for (int i = 7; i >= 0; i--) 
		cout << getBit(num,i) << " ";
	cout << endl;

	return 0;
}

Output is:

Input
0 0 0 1 0 0 0 0
Setting 6-th bit
0 1 0 1 0 0 0 0
Unsetting (Clearing) 4-th bit
0 1 0 0 0 0 0 0


Displaying an Integer with Bits - (A)
#include <iostream>
#include <iomanip>
using namespace std; 
 
void binary(unsigned int u) 
{ 
	int upper;
	if(u < 256)
		upper = 128;
	else
		upper = 32768;

	cout << setw(5) << u << ": ";

        // check if bit is set starting from the highest bit
        // (ex) upper = 128, 10000000, 01000000, 00100000, ..., 00000001

	for(int i = upper; i > 0; i = i/2) {
		if(u & i) 
			cout << "1 "; 
		else 
			cout << "0 "; 
	}
	cout << "\n"; 
}

int main() 
{
	binary(5);
	binary(55);
	binary(255);
	binary(4555);
	binary(14555);
	return 0;
}

Output is:

    5: 0 0 0 0 0 1 0 1
   55: 0 0 1 1 0 1 1 1
  255: 1 1 1 1 1 1 1 1
 4555: 0 0 0 1 0 0 0 1 1 1 0 0 1 0 1 1
14555: 0 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1


Displaying an Integer with Bits - (B) Using bitset

We can use <bitset> to display an integer in bits:

#include <iostream>
#include <iomanip>
#include <bitset>

using namespace std; 

void binary(unsigned int u) 
{ 
	cout << setw(5) << u << ": ";
        cout << bitset<16>((int)u);
	cout << "\n"; 
}

int main() 
{
	binary(5);
	binary(55);
	binary(255);
	binary(4555);
	binary(14555);
	return 0;
}

Output is:

    5: 0000000000000101
   55: 0000000000110111
  255: 0000000011111111
 4555: 0001000111001011
14555: 0011100011011011


Converting Decimal to Hex
#include <iostream>
using namespace std;

/* hex with leading zeros */
void decToHex(int n)
{
	char *hexString = "0123456789ABCDEF";

	cout << "decimal: " << n << endl;    
	cout << "hex    : ";
	for (int i = 2*sizeof(int) - 1; i >= 0; i--)
            cout << hexString[(n >> i*4) & 0xF];
	cout << endl << endl;
}

int main() {
	decToHex(10);
	decToHex(100);
	decToHex(1000);
	return 0;
}

Output is:

decimal: 10
hex    : 0000000A

decimal: 100
hex    : 00000064

decimal: 1000
hex    : 000003E8


The Number of Bits Set in an Integer (Number of Ones)

This code gets the number of bits set to 1 in an integer. In other words, it counts the number of one.

bitCountA() is an O(n), where n is the size, in bits, of an integer, while bitCountB() is an O(m), where m is the number of 1's in the solution. 

#include <iostream>

using namespace std;

void binary(unsigned int n)
{
	int upper = 256;
	for(int i = upper; i > 0; i = i/2) {
		if(n & i) 
			cout << " 1";
		else
			cout << " 0";
	}
	cout << endl;
}

/* O(n), where n is the size, in bits, of an integer */
int bitCountA(int n)
{
	int count = 0;
	while(n) {
		if(n & 1) count++;
		n = n >> 1;
	}
	return count;
}

/* O(m), where m is the number of 1's in the solution. */
int bitCountB(int n)
{
	int count = 0;
	while(n) {
		n = n & (n-1);
		count++;
	}
	return count;
}


int main()
{
	int a;

	a = 250;
	binary(a);
	cout << "Bit count = " << bitCountA(a) << endl;

	a = 250;
	binary(a);
	cout << "Bit count = " << bitCountB(a) << endl;
	return 0;
}

Output is:

 0 1 1 1 1 1 0 1 0
Bit count = 6
 0 1 1 1 1 1 0 1 0
Bit count = 6


The Bit Set Position of an Integer

This code stores the positions of bits set to 1 in an integer.

#include <iostream>

using namespace std;

void binary(unsigned int n)
{
	for(int i = 256; i > 0; i = i/2) {
		if(n & i) 
			cout << " 1";
		else
			cout << " 0";
	}
	cout << endl;
}

int bitCount(int n)
{
	int count = 0;
	while(n) {
		if(n & 1) count++;
		n = n >> 1;
	}
	return count;
}

void bitSetPos(int n, int a[])
{
	int ic = 0;
	for(int i = 0; i < 32; i++) {
		if(n & 1) a[ic++] = i;
		n = n >> 1;
	}
}

int main()
{
	int num = 100;
	int bc, nbit;
	int *a;

	/* get bit count */
	nbit = bitCount(num);
	/* array to store the bit set postion */
	a = new int[nbit];
	/* display the integer in bits */
	binary(num);
	/* get the position of bit set */
	bitSetPos(num,a);

	cout << "bit set position " << endl;
	for(int i = 0; i < nbit; i++) {
		cout << a[i] << " ";
	}
	cout << endl;

	delete [] a;

	return 0;
}

Output is:

 0 0 1 1 0 0 1 0 0
bit set position
2 5 6


In-Place Integer Swap with Bit Manipulation

This code swaps two integers in place using exclusive or (xor).

#include <iostream>

using namespace std;

void inplace_swap_A(int &a, int &b)
{
	a = b - a;
	b = b - a;
	a = a + b;
}

// Using xor property: a^b^b => a
void inplace_swap_B(int &a, int &b)
{
	a = a ^ b;	// a holds a_old ^ b_old
	b = a ^ b;	// b holds a_old which is (a_old ^ b_old) ^ b_old
	a = a ^ b;	// this line means a <--  (a_old ^ b_old) ^ a_old 
			// since b holds a_old.
			// So, as a result, a gets the value of b_old.
}

int main()
{
	int a = 10, b = 20;
	cout << "init values:  a = " << a << " b = " << b << endl;

	inplace_swap_A(a,b);
	cout << "swap A:  a = " << a << " b = " << b << endl;

	a = 100, b = 200;
	cout << "init values:  a = " << a << " b = " << b << endl;

	inplace_swap_B(a,b);
	cout << "swap B:  a = " << a << " b = " << b << endl;

	return 0;
}

Output from the run is: 

init values:  a = 10 b = 20
swap A:  a = 20 b = 10
init values:  a = 100 b = 200
swap B:  a = 200 b = 100


The Number of Bits Required to Convert an Integer A to Integer B

This problem is surprisingly straightforward.
It's just a matter of figuring out which bits in two numbers are different.
It's an exclusive or, xor.

#include <iostream>
#include <iomanip>
using namespace std; 
 
int convertAtoB(int a, int b) 
{ 
	int c = a ^ b;
	int count = 0;

	while(c != 0) {
		count += c & 1;
		c = c >> 1;
	}
	return count;
}

void binary(unsigned int u) 
{ 
	int upper;
	if(u < 256)
		upper = 128;
	else
		upper = 32768;

	cout << setw(3) << u << ": ";
	for(int i = upper; i > 0; i = i/2) 
		if(u & i) 
			cout << "1 "; 
		else 
			cout << "0 "; 
	cout << "\n"; 
}

int main() 
{
	int a,b;
	a = 8;
	b = 4;
	binary(a);binary(b);
	cout << "# of bit required = " << convertAtoB(a,b) << endl;
	cout << endl;

	a = 128;
	b = 25;
	binary(a);binary(b);
	cout << "# of bit required = " << convertAtoB(a,b) << endl;
	cout << endl;

	a = 10;
	b = 254;
	binary(a);binary(b);
	cout << "# of bit required = " << convertAtoB(a,b) << endl;
	cout << endl;

	return 0;
}

Output is:

  8: 0 0 0 0 1 0 0 0
  4: 0 0 0 0 0 1 0 0
# of bit required = 2

128: 1 0 0 0 0 0 0 0
 25: 0 0 0 1 1 0 0 1
# of bit required = 4

 10: 0 0 0 0 1 0 1 0
254: 1 1 1 1 1 1 1 0
# of bit required = 5


Swap Odd and Even Bits in an Integer

Masking even bits with 0xaa, then shift right. Mask odd bits with 0x55, then shift left. Then OR them. 

#include <iostream>
#include <iomanip>
using namespace std; 
 
void binary(unsigned int u) 
{ 
	int upper;
	if(u < 256)
		upper = 128;
	else
		upper = 32768;

	cout << setw(3) << u << ": ";
        
	for(int i = upper; i > 0; i = i/2) 
		if(u & i) 
			cout << "1 "; 
		else 
			cout << "0 "; 
	cout << "\n"; 
}

int swapEvenOddBits(int n)
{
	return ( ((n & 0xaa) >> 1) | ((n & 0x55) << 1) );
}

int main() 
{
	int n = 180;

	cout << "Original integer" << endl;
	binary(n);
	cout << endl;
	cout << "Ending with 0xaa" << endl;
	binary(n & 0xaa);
	cout << endl;
	cout << "Right shift for even bits" << endl;
	binary((n & 0xaa) >> 1);
	cout << endl;
	cout << "Ending with 0x55" << endl;
	binary(n & 0x55);
	cout << endl;
	cout << "Left shift for odd bits" << endl;
	binary((n & 0x55) << 1);
	cout << endl;

	cout << "Call swapEvenOddBits" << endl;

	/* Swap bits */
	binary(  swapEvenOddBits(n)  );

	return 0;
}

Output is:


Original integer
180: 1 0 1 1 0 1 0 0

Ending with 0xaa
160: 1 0 1 0 0 0 0 0

Right shift for even bits
 80: 0 1 0 1 0 0 0 0

Ending with 0x55
 20: 0 0 0 1 0 1 0 0

Left shift for odd bits
 40: 0 0 1 0 1 0 0 0

Call swapEvenOddBits
120: 0 1 1 1 1 0 0 0


What (n & (n-1) == 0) is checking?

n & (n-1) == 0 means that n and n-1 never share a 1 for any bits.

So, for example, suppose n and n-1 look like this.

n   = abcde1000
n-1 = abcde0111

abcde must be all 0s, which means that n must look like:

000001000

n is a power of two.

So, (n & (n-1) == 0) is checking if n is a power of 2.



Two's Complement

In computer, every bit is mapped representing something. Let's limit our discussion to 8 bits (1 byte). The number 7 is expressed by the following bit pattern:

00000111 (7)

How about -7? If we use the Most Significant Bit (MSB) as a sign bit, and let the value of 1 represent (-) sign. Then, -7 will have the following bit pattern:

10000111 (-7)

However, when we do an addition of the two, it does not become 0:

00000111 +
10000111
--------
10001110

So, how we make the sum of the two be zero?

00000111 +
1xxxxxxx
--------
00000000

We can find the x's easily:

00000111 +
11111001
--------
00000000

Notice that we can get 

11111001
by adding 1 after inverting all the bits in 00000111 (7):

11111000 +
00000001
--------
11111001

Invert a bit pattern of a number, and then add 1. The resulting number is the two's complement of the number.

So, the two's complement satisfies basic arithmetic, but one's complement (The resulting number by changing just the sign bit) does not.


Here is a simple way of getting two's complement:

action sample 1 sample 2
Starting from the right, find the first '1' 0101001 0101000
Invert all of the bits to the left of that one 1010111 1011000

Here is 8 bit two's complement:

binary two's complement unsigned
00000000 0 0
00000001 1 1
... ... ...
01111110 126 126
01111111 127 127
10000000 -127 129
... ... ...
11111110 -2 254
11111111 -1 255

Here is an additional question.
What's the representation of bit pattern for short -1?
Hint: adding 1 should turn off all the bits (because -1 + 1 = 0) and short needs 2 bytes.

The answer is 11111111 11111111.




Fliping n-th bit of an integer

This example is for the little-endian byte order case.
Note that XOR against 1 flips a bit. Check Bitwise Operations 

#include <iostream>
#include <iomanip>
using namespace std; 
 
void binary(unsigned int u) 
{ 
	int upper;
	if(u < 256)
		upper = 128;
	else
		upper = 32768;

	cout << setw(5) << u << ": ";
	for(int i = upper; i > 0; i = i/2) {
		if(u & i) 
			cout << "1 "; 
		else 
			cout << "0 "; 
	}
	cout << "\n"; 
}

void bit_flip(int& m, int nth)
{
	m ^= 1 << nth;
}

int main() 
{
	int m = 12;
	int nth = 2;
	binary(m);
	cout << "   flip " << nth << "th bit of " << m << endl;
	bit_flip(m,nth);
	binary(m);
	cout << endl;

	m = 63;
	nth = 6;
	binary(m);
	cout << "   flip " << nth << "th bit of " << m << endl;
	bit_flip(m,nth);
	binary(m);

	return 0;
}

Output is:

   12: 0 0 0 0 1 1 0 0
   flip 2th bit of 12
    8: 0 0 0 0 1 0 0 0

   63: 0 0 1 1 1 1 1 1
   flip 6th bit of 63
  127: 0 1 1 1 1 1 1 1


Floating Point Number Bit Pattern

floating_bit_pattern

Question A: What's the bit pattern of the following?

int i = 25;
float f = *(float*)&i;

Note that the last line does not evaluate the value i but the location of i. So, whatever the bit pattern of the integer representing the address of i (&i) considered as a bit pattern representing floating point number, *(float*).

very_small_number

Question B: What's the bit pattern of the following?

float f = 25.0;
short s = *(short*)&f;
short_number

The &f is pointing to the starting address of 4 byte floating number. But when we cast it with (short*)&f, compiler thinks "I was wrong. The address is not representing a 4-byte floating point number but a short type." So, whatever bit pattern happend to reside in the first two bytes is now representing 2-byte short integer type. So, when we dereference it with *(short*)&f, we won't get the value we want which is 25.



Bit pattern palindrome of an integer

Following example tells if the bit pattern of an interger is a palindrome or not. It first saves the integer to bitset, and the compare (xor) the bit pattern starting from both ends.

#include <iostream>
#include <bitset>

using namespace std;

const int Max = 8*sizeof(int);

bool isPalindrome(int n)
{
	bool palindrome = true;
	bitset<Max> b = n;
	for(int i = 0; i < Max/2 - 1; i++) { 
		if(b[i] ^ b[Max-1-i]) {
			palindrome = false;
			break;
		}
	}
	return palindrome;
}

int main()
{
	int m;
	m = (1 << (Max-1)) + (1 << 0);
	cout << bitset<Max> (m) << endl;
	cout << "palindrome: " << isPalindrome(m) << endl;

	m = (1 << (Max-1)) + (1 << 1);
	cout << bitset<Max> (m) << endl;
	cout << "palindrome: " << isPalindrome(m) << endl;

	m = (1 << (Max-2)) + (1 << 1);
	cout << bitset<Max> (m) << endl;
	cout << "palindrome: " << isPalindrome(m) << endl;

	m = (1 << (Max-6)) + (1 << 11);
	cout << bitset<Max> (m) << endl;
	cout << "palindrome: " << isPalindrome(m) << endl;

	m = (1 << (Max-2)) + (1 << (Max-3)) + (1 << 2) + (1 << 1);
	cout << bitset<Max> (m) << endl;
	cout << "palindrome: " << isPalindrome(m) << endl;

	return 0;
}

Output is:

10000000000000000000000000000001
palindrome: 1
10000000000000000000000000000010
palindrome: 0
01000000000000000000000000000010
palindrome: 1
00000100000000000000100000000000
palindrome: 0
01100000000000000000000000000110
palindrome: 1




Portable way to obtain the most significant byte
Which one is the most portable way to obtain the most significant byte of an unsigned integer i?
(a) i & 0xFF00 
(b) i >> 24 
(c) i & 0xFF000000 
(d) i >> (CHAR_BIT * sizeof(int) - 1))
(e) i >> (CHAR_BIT * sizeof(int) - 3))

My answer: (d)
(a)-(c) does not cover sizeof(int), (d) 3 is wrong.
(d) is comprehensive because of CHAR_BIT (some implementation has 7 bits for char), sizeof(int)(4,8,16 byte int), and right shift works regardless of Endianness (it always shift bits towards least significant).


NaeSoSan


Full List of C++ Tutorials