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

## Saturday, January 8, 2011

### Bit Operation #9

Print out odd numbers from 1 to 100

### 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 #6

Extract a single bit from a character.

Extract a range of bits 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);

}

## Friday, January 7, 2011

### Bit Operation #5

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

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

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?

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?

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

int bitCount(unsigned int a)

{

int count = 0;

while (a != 0)

{

count += a & 0x01;

a >>= 1;

}

return count;

}

## Thursday, January 6, 2011

### Bit Operation #3

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

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

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)

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.

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

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.

int f(unsigned int x)

{

return !(x & (x-1));

}

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)

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.

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.

Subscribe to:
Posts (Atom)