C++ Tutorial Quiz - Bit Manipulation - 2020

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:

1. myBits ^ 0 : No change
2. 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 << 3
--------
8 * (1 << 3)
--------
8 * (2**3)
--------
64

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

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

Example 2:
Write a macro with two arguments a and pos, where a is a byte and the pos specifies a bit position of the byte. The macro should clear the particular bit position in the given byte.

#include <stdio.h>
using namespace std;

/* bit clear: 
  1st arg: int, 2nd arg: bit position to clear */
#define CLEARBIT(a, pos) (a &= ~(1 << pos) )

int main()
{
	/* 'z': decimal value 122 (=01111010) */
	char a = 'z';  

	/* clearing the 5th bit */
	char aOut = CLEARBIT(a, 5);

	/* aOut = 'Z': decimal value 90 (=01011010) */
	printf("aOut=%c\n", aOut);

	return 0;
}

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

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

The right/left most byte
assuming 16 bit, 2-byte short integer:

unsigned char right = val & 0xff; // right most (least significant) byte
unsigned char left = (val>>8) & 0xff; // left most (most significant) byte

sign bit
assuming 16 bit, 2-byte short integer, two's complement:

bool sign = val & 0x8000; // sign 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

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 

Let's look at the diagram for 4-bit number system:

We have two issues: (two 0s and (+1)+(-1) is not zero).

Then, 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

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.

To get negative representation of any integer, take bitwise complement and then add one!

	
 ~x + 1 = -x 

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:

Here is 8 bit two's complement:

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.

Source A

#include <iostream>
using namespace std;

/* if the dereferenced pointer is 1, the machine is little-endian 
   otherwise the machine is big-endian */

int endian() {
	int one = 1;
	char *ptr;
	ptr = (char *)&one;
	return (*ptr);
}

int main()
{
	if(endian()) 
		cout << "little endian\n";
	else
		cout << "big endian\n";
}

Source B

#include <iostream>
using namespace std;

int endian() {
	union {
		int one;
		char ch;
	} endn;

	endn.one = 1;
	return endn.ch;
}

int main()
{
	if(endian()) 
		cout << "little endian\n";
	else
		cout << "big endian\n";
}

It is tempting to use bit operation for this problem. However, bit shift operator works on integer, not knowing the internal byte order, and that property prevents us from using the bit operators to determine byte order.

To check out the endian, we can just print out an integer (4 byte) to a 4-character output with the address of each character.

#include <stdio.h>

int main()
{
	int a = 12345; // x00003039
	char *ptr = (char*)(&a;);
	for(int i = 0; i < sizeof(a); i++) {
		printf("%p\t0x%.2x\n", ptr+i, *(ptr+i));
	}
	return 0;
}

Output:

0088F8D8        0x39
0088F8D9        0x30 
0088F8DA        0x00
0088F8DB        0x00

As we see from the output, LSB (0x39) was written first at the lower address, which indicate my machine is little endian.

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*).

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

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

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.

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

(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), (e) 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).

Here is an example that shows output of 3 integers with field width 5 and left aligned.

// Russian Peasant Multiplication 

#include <iostream>
#include <iomanip>
using namespace std;

int RussianPeasant(int a, int b)
{
	int x = a,  y = b;
	int val = 0;
	cout << left << setw(5) << x << left << setw(5) << y << left << setw(5) << val << endl;
	while (x > 0) {
		if (x % 2 == 1) val = val + y;
		y = y << 1;  // double
		x = x >> 1;  // half
		cout << left << setw(5) << x << left << setw(5) << y << left << setw(5) << val << endl; 
	}
	return val;
}

int main() {
	RussianPeasant(238, 13);
	return 0;
}

The output should look like this:

238  13   0
119  26   0
59   52   26
29   104  78
14   208  182
7    416  182
3    832  598
1    1664 1430
0    3328 3094

Actually, the multiplication is known as Russian Peasant Multiplication. Whenever x is odd, the value of y is added to val until x equals to zero, and then it returns 3094.

How may operations for addition?
Notice that we're adding y to val only when x is odd.

Let's make the table. 1st column is for x, the 2nd column indicates whether odd or even, and the 3rd column is the representation of the binary bit of the 2nd column:

So, how many 1's in the 2nd column? Yes, 6 times operations for addition. Another interesting fact is that if we sum all the red numbers in the 2nd column, it is none other than the original number, 238(=128+64+32+8+4+2).

Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB memory. Follow up with what you would do if you have only 10 MB of memory.

1GB = 8 billion bits. So, with those bits, we can map all 4 billion integers (actually, 2147483648 non-negative integers). We'll use integer arrays a[1+N/32] because an integer has 32bits.

For example, whenever we encounter a number n, we switch the bit for that nth-bit:

10: ....00000000 00000000 00000000 00000010 00000000
16: ....00000000 00000000 00000000 10000010 00000000
35: ....00000100 00000000 00000000 10000010 00000000
     a[1]        a[0] ->

Here is the code for N = 100, and in this case, we need only 4 integer arrays (4x32 > 100)

#include <stdio.h>

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F // 31(=00011111): mask for 32 bit int
#define N 100
int a[1 + N/BITSPERWORD];

/* 1 << (i & MASK): left shift from 0 to 31, represents 2^i
   i >> SHIFT: array index
               0-31   a[0]
	       32-63  a[1]
               64-95  a[2]
               ...    ...
*/

void setBit(int i) { a[i>>SHIFT] |=  (1<<(i & MASK)); }
void clearBit(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  testBit(int i){ return  a[i>>SHIFT] & (1<<(i & MASK)); }

int main(void)
{  
    FILE *f = fopen("integers.txt","r");
    int i;
    for (i = 0; i < N; i++)
        clearBit(i);

    printf("--input--\n");
    while (fscanf(f,"%d", &i;) != EOF) {
	printf("%d%s", i,",");
        setBit(i);
    }

    printf("\n--output\n");
    for (i = 0; i < N; i++)
        if (!testBit(i)) 
            printf("%d%s", i,",");        
	        
    return 0;
}

Output:

--input--
1,3,5,81,55,60,99,
--output
0,2,4,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,56,57,58,59,
61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,82,83,84,85,86,87,88,
89,90,91,92,93,94,95,96,97,98,

In the code, what the i << SHIFT in a[i << SHIFT] is doing?
It gives us the array index. For example when SHIFT=5 case (32-bit integer):

31  00011111  =>  000 is the index(=0)
32  00100000  =>  001 is the index(=1)
63  00111111  =>  001 is the index(=1)
64  01000000  =>  010 is the index(=2)
95  01011111  =>  010 is the index(=2)
96  01100000  =>  011 is the index(=3)

Also, 1<<(i & MASK)) sets the bit for a given index, i, and actually, the value of (i & MASK) ranges from 0 to 31 which is the relative bit location for each array element i.

Write a routine to flash a LED every one second. Use delay(ms) for delay. Bit-4 (16 bit total), Active Low (i.e Off=1, ON=0)

#include <stdio.h>
#include <stdint.h>

#ifdef _WIN32
	#include <windows.h>
	void sleep(unsigned milliseconds)
	{
		Sleep(milliseconds);
	}
#else
	#include <unistd.h>
	void sleep(unsigned milliseconds)
        {
                usleep(milliseconds * 1000); 
        }
#endif

// print dec in binary 
void printBinary(uint16_t a)
{
        // 16 bit print
	for(uint16_t i = 32768; i > 0; i = (i>>1)) {
		if(a & i)
			printf("1");
		else
			printf("0");
	}
	printf("\n");
}

void LedFlash()
{
	volatile 
		uint16_t a = (uint16_t)0;
	while(1) {
                // bit-4
		a ^= (1 << 4);
		printBinary(a);
		sleep(1000); //1 sec delay
	}
}

int main()
{
	LedFlash();
	return 0;
}

Output:

0000000000010000
0000000000000000
0000000000010000
0000000000000000
0000000000010000
....

In this example, we're trying to store card information with minimal space usage (using only 6 bits). The face value (1-13) will be stored at 0-3th bits and the suit info at 4-5th bits. As shown in the mask pictures below, we're using two bit masks: Suit & Value:

The following code handles two questions: (1) Same suit? (2) Is the face value of the first card is greater than the second card?

#include <iostream>
using namespace std;

#define SUIT_MASK  0x30
#define VALUE_MASK 0x0F


enum Suit {
	CLUBS = 0,       // x00
	DIAMONDS = 16,   // x10
	HEARTS = 32,     // x20
	SPADES = 48      // x30
};

typedef struct Card {
   enum Suit suit;
   unsigned int value;
} Hand;

 
bool sameSuit(Suit c1, Suit c2) 
{
	return (! ((c1 & SUIT_MASK) ^ (c2 & SUIT_MASK)));
}

bool greaterValue(unsigned int c1, unsigned int c2) 
{
	return ((unsigned int)(c1 & VALUE_MASK) >
          (unsigned int)(c2 & VALUE_MASK));
}

int main()
{
	Hand hand[5] = {{CLUBS, 1}, {SPADES, 5}, {DIAMONDS, 10}, {HEARTS, 5}, {CLUBS, 3}};
	cout <<  " same suit= " << sameSuit(hand[0].suit, hand[1].suit) << endl;
	cout <<  " same suit= " << sameSuit(hand[0].suit, hand[4].suit) << endl;
	cout <<  " greater value= " << greaterValue(hand[1].value, hand[2].value) << endl;
	cout <<  " greater value= " << greaterValue(hand[1].value, hand[4].value) << endl;
	return 0;
}

Output:

 same suit= 0
 same suit= 1
 greater value= 0
 greater value= 1

Write a code that finds the minimum integer from two integers without any comparison. Also, any if/else is not allowed.

#include <iostream>
using namespace std;

int getSignBit(int n)
{
	int sign = (n >> 31) & 0x01;;
	return sign;
}

// returns the maximum 
// without using any comparison and if/else statements
int getMax(int a, int b)
{
	int signa, signb;
	
	// a >= b : signa = 1, signb = 0;
	// a < b : signa = 0, signb = 1;
	signb = getSignBit(a-b);
	signa = signb ^ 1;
	return signa*a + signb*b;
}

int main()
{
	int m = 215, n = 215;
	cout << getMax(m,n) << endl;
	return 0;
}

Finding the number of different symbols between two same length strings.

The following code initially does exclusive-or (xor) of the the two strings, and then count the bits with 1 which is a process of clearing bits.

#include <iostream>

int hamming(unsigned int i, unsigned int j)
{
    int distance = 0;
    unsigned int val = i ^ j;
    while(val) {
       distance++;
       val &= val - 1;
    }
    return distance;
}

int main()
{
    /* 18 = 10010
       30 = 11110 */
    std::cout << hamming(18, 30);    // = 2
}

For more on bit related code, Bit Twiddling Hacks