# 13. Bit Manipulation¶

By now you have seen all constructs of C programming language. In this chapter we will study bit-manipulation using operators provided by C. Bit manipulation is considered low-level programming can result in hard to read code but can improve performance significantly if done right. Most of the bit manipulation involve numbers and in few cases you can apply it to characters because characters are internally integers. The key to bit-manipulation is bitwise operators &, ^, |, !, ~ << and >> operators which stand for AND, XOR, OR, NOT, bit-flipping, left-shift and right-shift operators. Given below is truth table for AND, XOR, and OR gate for quick reference.

In C, 0 represents false and any non-negative value represents true. Note that both are keywords.

p | q | p & q |
---|---|---|

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

**AND Gate’s Truth Table**

p | q | p | q |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 1 |

**OR Gate’s Truth Table**

p | q | p ^ q |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

**EXOR(known as XOR as well) Gate’s Truth Table**

As you may know there are two gates NAND and NOR which are universal gates i.e. all other gates can be constructed by using only NAND or only NOR gates. C does not have any operators but that can be easily constructed using NOT operator(!) with AND and OR operator. NOT gate which is implemented by NOT operator makes true to false and false to true. Given below are their truth tables:

p | q | !(p&q) |
---|---|---|

0 | 0 | 1 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

**NAND Gate’s Truth Table**

p | q | !(p|q) |
---|---|---|

0 | 0 | 1 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 0 |

**NOR Gate’s Truth Table**

The shift operators shift bits to left or right. For example, 1<<2 means \(1^2\). Similarly, 23>>3 means \(\frac{23}{2^3}\). How this works is that say we have a number 1 represented by 8 bits then it would be 00000001 and when we say 1<< then bits are shifted to left and right side is filled with 0 thus it becomes 00000010 or 2 which is as good as multiplying by 2. If we say 1<<2 then bits are shifted to left by 2 position which means the sequence will become 00000100 i.e. which is multiplication with 4.

## 13.1. Basics¶

We have discussed this briefly in chapter of “Structures and Unions”. I would
like to present that here as well. If the bytes for any data type occupy
multiple bytes and bytes start with least significant byte on lower address
then it is a little endian machine and reverse ordering means it is a big
endian machine. Consider the 32-bit number `0x04030201`

whose address is `0xX`

then it would look like following in memory.

```
adr: 0xX 0xX+1 0xX+2 0xX+3
mem: 0x4 0x3 0x2 0x1 // big endian
mem: 0x1 0x2 0x3 0x4 // little endian
```

The difference becomes evident if you want to cast it to some lower type. Let
us say above value is `V`

and we cast it to a `char c`

as ```
char c =
*(char*)&V;
```

then for big endian machines it will be `0x1`

and for little
endian machine it will be `0x4`

. Note that nowadays popular architecture like
x86 are little endian but network bytes are big endian thus to write portable
code people generally transfer bytes from host to network by calling functions
`hton`

. Discussion of such functions is out of scope of this book but this
should give you a hint.

## 13.2. Shifts and division¶

We have studied that right shift and division are same but that is not entirely true. Consider the following code:

```
#include <stdio.h>
int main()
{
int i = 0xffffffff; // all bit one
unsigned int ui = 0xffffffff; // again all bits one
printf("%d %u\n", i>>1, ui>> 1);
return 0;
}
```

we compile it to object code using the command `$gcc -c test.c`

where
`test.c`

is the filename to which we saved the source. Now we see assembly
source using the command `objdump -d -M gas -S test.o`

and we have the
following:

```
test.o: file format elf64-x86-64
Disassembly of section .text:
0000000000000000 <;main>:
0: 55 push %rbp
1: 48 89 e5 mov %rsp,%rbp
4: 48 83 ec 10 sub $0x10,%rsp
8: c7 45 f8 ff ff ff ff movl $0xffffffff,-0x8(%rbp)
f: c7 45 fc ff ff ff ff movl $0xffffffff,-0x4(%rbp)
16: 8b 45 fc mov -0x4(%rbp),%eax
19: d1 e8 shr %eax
1b: 89 c2 mov %eax,%edx
1d: 8b 45 f8 mov -0x8(%rbp),%eax
20: d1 f8 sar %eax
22: 89 c6 mov %eax,%esi
24: bf 00 00 00 00 mov $0x0,%edi
29: b8 00 00 00 00 mov $0x0,%eax
2e: e8 00 00 00 00 callq 33 <main+0x33>
33: b8 00 00 00 00 mov $0x0,%eax
38: c9 leaveq
39: c3 retq
```

As you can clearly see signed integer is getting an `shr`

instruction while
unsigned integer is getting an `sar`

instruction which causes -1 to remain -1
while unsigned number is divided by 2. These two are known as logical and
arithmetic shifts. The difference can cause you to debug your program for
several hours. In other words, division with signed types rounds toward zero,
as one would expect, but right shift is a division (by a power of 2) that
rounds to \(-\infty\). The arithmetical shift (`sar`

in the above
fragment) fills in ones or zeros, according to the most significant bit of the
original number.

Note that the C standard leaves the behavior of a right shift of a signed
integer as “implementation-defined”. The behavior shown (that a negative value
remains negative after right shift for signed integers) is the default behavior
of `gcc`

. This is clearly stated in subclause 5 of iso.6.5.7.

## 13.3. 2’s Complement¶

Consider the following program:

```
#include <stdio.h>
#include <limits.h>
int main()
{
int i = INT_MIN; // 0xa0000000
printf("%d\n", i);
if(i < 0)
i = -i;
printf("%d\n", i);
return 0;
}
```

and the output is not trivial to guess. The output is:

```
-2147483648
-2147483648
```

As I had told that 0 and -0 have same representation in 2’s complement in our
first chapter. But even `INT_MIN`

or for that matter `LONG_MIN`

or
`LLONG_MIN`

will have same representation as their negative of `INT_MIN`

or
`LONG_MIN`

or `LLONG_MIN`

. This is the reason why the above code does not
work as expected. For this reason alone following program prints negative
number where family of absolute-value funcitons fail.

```
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int main()
{
int n;
printf("In this program we will try to compute absolute value for integers entered.\n");
scanf("%d", &n);
printf("%d\n", abs(n));
printf("Now is the time for surprise.\n");
printf("%d %ld %Ld\n", abs(INT_MIN), labs(LONG_MIN), llabs(LLONG_MIN));
return 0;
}
```

This entire chaos erupts because since the numbers are split into two ranges
and 0 unbalances it thus `INT_MIN`

has an absolute value larger than
`INT_MAX`

. The same applies for other integral data types as well.

Another issue with shifts is that you cannot shift for entire width of the data type. For example, consider the following program on a 64-bit computer

```
#include <stdio.h>
int main()
{
unsigned int i = 0;
unsigned long l = 0;
printf("%u %lu\n", i>>32, l>>64);
return 0;
}
```

and `gcc`

will immediately give you following warnings with `-Wall`

flag:

```
test.c: In function ‘main’:
test.c:5:3: warning: right shift count >= width of type [enabled by default]
printf("%d \n", ~0 >> 32);
^
test.c:6:3: warning: right shift count >= width of type [enabled by default]
printf("%ld \n", ~0UL >> 64);
^
```

However, we are lucky that output is consistent in both the cases and is 0 at least on my Intel CPU. This may not be the case on other CPUs thus be careful when you want to shift a number which is equal or greater than the width of that type.

## 13.4. Average of two numbers¶

Let us consider calculation of average of two unsigned integers. A naive approach is given below:

```
#include <stdio.h>
int main()
{
unsigned int i =100;
unsigned int j = 100;
printf("%u\n", (i+j)/2);
return 0;
}
```

Now as you can easily guess output would be 100 but if the sum is greater than
`UINT_MAX`

then it will cause integer overflow which is not a desirable
case. Another better but still naive argument would be to cast these to higher
data type such as unsigned long. The problem is that you cannot cast ```
unsigned
long long
```

to a higher data type as it is already highest. The previous
program can be modified to compute it without overflowas given below:

```
#include <stdio.h>
#include <stdlib.h>
int main()
{
unsigned int i =100;
unsigned int j = 100;
printf("%u\n", (i & j) + ((i ^ j)>>1));
return 0;
}
```

Another way to compute this is given below:

```
#include <stdio.h>
int main()
{
unsigned int i =100;
unsigned int j = 110;
printf("%u\n", i + abs((i - j))/2);
return 0;
}
```

However, this solution is not in sync with the theme of this chapter i.e. by bits manipulation.

If it is known that \(i\ge j\) then another solution is possible which is given below:

```
#include <stdio.h>
int main()
{
unsigned int i =100;
unsigned int j = 110;
printf("%u\n", (i | j) - ((i ^ j)>>1));
return 0;
}
```

## 13.5. Swapping two numbers without using a temporary¶

The solution of swapping two numbers without a temporary is well known using XOR operation. Given below is code:

```
#include <stdio.h>
int main()
{
unsigned int i =100;
unsigned int j = 110;
i = i ^ j;
j = i ^ j;
i = i ^ j;
printf("%u %u\n", i , j);
return 0;
}
```

and the output is not hard to guess, which, is

```
110 100
```

One more usage of this XOR gate can be toggling a number between two values as given below:

```
#include <stdio.h>
int main()
{
unsigned int i =100;
unsigned int j = 110;
unsigned int t = i ^ j;
unsigned int x = i;
x ^= t;
printf("%u %u\n", i , j);
return 0;
}
```

Here, output is not important but `x`

can toggle between `i`

and `j`

by
XORing with `t`

, which is pre-calculated.

## 13.6. Finding next even or odd number¶

It is trivial to compute next even or odd number using bitwise operations. A program to do that is given below:

```
#include <stdio.h>
int main()
{
unsigned int i =100;
printf("%u\n", (i | 1) + 1 );
printf("%u\n", (i - 1) & ~1 );
printf("%u\n", (i + 1) | 1);
printf("%u\n", (i & ~1) - 1);
return 0;
}
```

The output is self explanatory and you can deduce it yourself.

## 13.7. Operations on bits¶

### 13.7.1. Testing a bit¶

It is trivial to test a bit of a program. For example:

```
#include <stdio.h>
int main()
{
unsigned long i =100;
// 4th bit is tested
printf("%d\n", (i & (1UL << 4)) != 0);
// 6th bit is tested
printf("%d\n", (i & (1UL << 6)) != 0);
return 0;
}
```

### 13.7.2. Setting a bit¶

Once again it is trivial and you can draw analogy from previous program:

```
#include <stdio.h>
int main()
{
unsigned long i =100;
// 4th bit is set
printf("%d\n", (i | (1UL << 4)) != 0);
// 6th bit is set
printf("%d\n", (i | (1UL << 6)) != 0);
return 0;
}
```

### 13.7.3. Clearing a bit¶

Only code is enough again:

```
#include <stdio.h>
int main()
{
unsigned long i =100;
// 4th bit is cleared
printf("%lu\n", (i & ~(1UL << 4)));
// 6th bit is cleared
printf("%lu\n", (i & ~(1UL << 6)));
return 0;
}
```

### 13.7.4. Toggling a bit¶

```
#include <stdio.h>
int main()
{
unsigned long i =100;
// 4th bit is toggled
printf("%lu\n", (i ^ (1UL << 4)));
// 6th bit is toggled
printf("%lu\n", (i ^ (1UL << 6)));
return 0;
}
```

and the output is:

```
116
36
```

### 13.7.5. Copying bits¶

Say we have two positions in a number and we want to copy bits then following code will do that:

```
#include <stdio.h>
int main()
{
unsigned long i =100;
unsigned long x = ((i >> 6) ^ (i >> 4)) & 1; // one if bits are different
i ^= (x << 4); // change if bits are different
printf("%lu\n", i);
return 0;
}
```

6th bit of 100 is 1 while 4th is 0. Copying 6th bit to 4th position increases value by 16, which is nothing but \(2^4\) and thus our answer is 116.

### 13.7.6. Swapping even and odd bits of a number¶

Consider the following problem. In a given number(unsigned in nature) we want to move bits at position 0, 2, 4, 6, … to position 1, 3, 5, 7, … and bits at position 1, 3, 5, 7, … to position 0, 2, 4, 6 … then how would we achieve that.

The solution lies in the observation that bits can be extracted using bitwise
AND operation. Thus to extract bits at even position we need a number which is
all 1s at even position while 0s at at odd positions. Same analogy can be
applied for odd positions. Once we have extracted the numbers we can shift
number with even bits to left and second one to right. Thus now bits are at
proper position and ORing the two will give us desired result. Following code
does it for an `unsigned char`

. This type has been chosen for simplicity.

```
#include <stdio.h>
int main()
{
unsigned char uc =107; // bit sequence is 01101011 thus our
// desired sequence is 10010111 i.e. output as 151
unsigned char ue = 170; // bit sequence is 10101010
unsigned char uo = 85; // bit sequence is 01010101 note that sum
// of ue and uo is 255 which is UCHAR_MAX or maximum value for
// unsigned char
ue &= uc;
ue = ue >> 1;
uo &= uc;
uo = uo << 1;
uc = ue | uo;
printf("%u %u %u\n", uc, ue, uo);
return 0;
}
```

More of such problems which are specific to bits will be provided in data structures and algorithm book. For now basics have been explain as how to use basic bitwise operations which I believe is sufficient.