Bit Operation #9

Print out odd numbers from 1 to 100

void printOddNumber()
{
    for (int i = 1; i <= 100; ++i)
    {
        if (i & 0x01)
            cout << i << \n;
    }
}

Bit Operation #8

100000
100000
------
011111

000000
000000
------
000000

100000
000000
------
000000

000100
000100
------
111011

100100
100100
------
011011

100100
000100
------
111011

010101
101010
------
000000

111111
111111
------
000000

// A function using bitwise operators for above results. 
unsigned int f(unsigned int a, unsigned int b)
{
    if (a & b)
    {
        return ~(a & b); 
    }
    return 0;
}

Bit Operation #7

Find the largest possible integer

int largestInt()
{
    return ~0;
}

Bit Operation #6

Extract a single bit from a character.

int extractBit(char byte, unsigned int pos) 
{
    assert(pos < 8);

    return ((byte >> pos) & 1);
}

Extract a range of bits from a character.

char extractBitRange(char byte, unsigned int startPos, unsigned int offset) 
{
   assert((startPos + offset) < 8);
   return (byte >> startPos) & ~(0xfe << offset);
}

Bit Operation #5

How can we check whether a particular bit is ON (1) or OFF (0)?

bool checkBitOn(unsigned int num, unsigned int i)
{
   return (num & (1 << i));
}

How can we turn OFF a particular bit in a number?

unsigned int turnBitOff(unsigned int num, unsigned int i)
{
    return (num & (~(1 << i)));
}

For example, num = 00010111 and i = 4. (1<<4)==00010000 and ~(1<<4)==11101111. Hence, num&(~(1<<4))==00010111 & 11101111==00000111.

Then, how can we turn ON a particular bit in a number?

unsigned int turnBitOn(unsigned int num, unsigned int i)
{
    return (num | (1 << i));
}

Bit Operation #4

Let's think about how we can count the bit set to 1 in an integer?

 

int bitCount(unsigned int a)
{
    int count = 0;
    while (a != 0)
    {
        count += a & 0x01;
        a >>= 1;
    }
    return count;
}

Then, how can we optimize the process to work with several integers?

Bit Operation #3

Input parameter a is a 4 bits integer (e.g., "1100" or "1000").

int f(int a)
{
    int b = 0;
    while (a >>= 1)
    {
       b++;
    }
    return b;
}

case1> 1100 (b==0)->0110 (b==1)->0011 (b==2)->0001 (b==3)->0000 : return 3
case 2> 1000 (b==0)->0100 (b==1)->0010 (b==2)->0001 (b==3)->0000 : return 3

This function returns the position of the leftmost '1' bit in input a.

Now, let's consider when 'while' statement can be infinite. Zero, with no non-zero bit, returns 0. A negative number throws the computer into an infinite loop. See below.

Signed 4bits integer
+7 : 0111
+6 : 0110
+5 : 0101
+4 : 0100
+3 : 0011
+2: 0010
+1 : 0001
+0: 0000
0 : n/a
-0 : 1111
-1 : 1000
-2 : 1001
-3 : 1011
-4 : 1100
-5 : 1101
-6 : 1110
-7 : 1111

Unsigned 4 bits integer
+15 : 1111
:
+7 : 0111
:
+1 : 0001
+0 : n/a
0 : 0000

Bit Operation #2

Let's think about simple examples again.

Input: 4 bits integer x (e.g., 1010)

int f(unsigned int x)
{
    return !(x & (x-1));
}

We know that (x & (x-1)) operation erases the rightmost 1 bit in x. Now, consider an integer that is a power of two has exactly one bit that is '1'. Hence, if x contains only one bit that is '1', (x & (x-1)) will be zero (0000). After applying 'logical not' operation (!), a value of 0 becomes 1 and a value other than 0 becomes 0.

Therefore, this function returns whether an integer is a power of two. Consider one case where the input x is zero (0000). Then, this function returns 1 saying x is a power of two although zero is not a power of two. Hence, we have to modify this function as below.

int f(unsigned int x)
{
    return x && !(x & (x-1));
    // same to (x != 0) && !(x & (x-1));
}

Bit Operation #1

Bit operation is very often asked in job interviews and can be very tricky. Here, I am going to brush up bit operation problems that can be expected in my future job interviews.

Input: 4 bits integer x (e.g., 1010)

int f(unsigned int x)
{
    int a = 0;
    while (x != 0)
    {
        x = x & (x-1);
        ++a;
    }
    return a;
}

Let's think of what (x-1) is in the case of x = 1010. (x-1) is 1001 because the rightmost bit of 1 in x is changed to 0 and all 0 bits to the right are changed to 1. Look at this details.
1 0 1 0
      |  |
      v  v
1 0 0 1

We can easily get the result after applying & operation for x and (x-1).
    1 0 1 0
& 1 0 0 1
-----------
    1 0 0 0

Hence, the result of & operation in while statement shows that the rightmost 1 bit of x turns to 0. Finally, if we do this operation until x become zero (0000), the variable 'a' will count the number of 1 bit in x.