Systems Programming

Bit Twiddling

Aug 2013

• To understand the practical use of the bitwise operators.

1 Semantically-independent ways to represent data

1. Decimal: Good for humans, bad for programmers. Why? Try to convert from decimal to any other base and you'll see. For example, decimal to binary or decimal to hexadecimal.
   

   Figure 1.1 Obtaining the value from a decimal number (from [1])
2. Binary: Allow us to clearly see the internal representation of a value. However, binary is a long representation: just try to picture using a value such as 11110000101011100001010011101100...
3. Hexadecimal: Offers a good tradeoff between decimal and binary. As base 16 is a power of 2 (2⁴), the conversion between binary and hex is 4 binary digits to 1 hex (right aligned). For example, to convert the previous binary number to hex we just need to read the bits 4 at a time:

   // 1111 0000 1010 1110 0001 0100 1110 1100
   //   F    0    A    E    1    4    E    C
   

   Thus the hex value will be F0AE14EC, which is not only shorter but much more readable than the binary one. At the same time, it is equally simple to extract the bits from anywhere within the sequence. For those reasons, hex representation is widely used in low level programming.
   

   Figure 1.2 Obtaining the value from a hex number (from [1])

1.1 Representation of hex numbers in C

unsigned int var;
var = 254;
var = 0xFE;

1.2 Output of hex values

printf("%x\n", hex);  // fe
printf("%X\n", hex);  // FE

2 Bitwise operators

2.1 Logical operators

2.1.1 Bitwise AND

2.1.2 Bitwise OR

2.1.3 Bitwise NOT

2.1.4 Bitwise XOR

2.2 Shifting operators

2.2.1 Left logical shift

Figure 2.1 Bitwise shifting to the left (from [2])

unsigned char x = 0x17;   // 23 in decimal
unsigned char y = x << 1; // left shift by 1 bit
// now y will store 46 (0x2E)

y = x << 2; // y will store 92  (0x5C)
y = x << 3; // y will store 184 (0xB8) 

2.2.2 Right logical shift

Figure 2.2 Bitwise shifting to the right (from [3])

unsigned char x = 0x17;   // 23 in decimal
unsigned char y = x >> 1; // right shift by 1 bit
// now y will store 11 (0x0B)

y = x >> 2; // y will store 5 (0x5)
y = x >> 3; // y will store 2 (0x2) 

2.3 The sizeof operator

printf("sizeof(int)    = %d\n", sizeof (int));
printf("sizeof(char)   = %d\n", sizeof(char));
printf("sizeof(float)  = %d\n", sizeof(float));
printf("sizeof(double) = %d\n", sizeof(double));

Exercise:

1. unsigned int clear(unsigned int val): clear all bits of the value
2. unsigned int setbit (unsigned int x, int bit): where bit must be a number between 0 and 31. The function should turn on the desired bit in x.
3. unsigned int clearbit (unsigned int x, int bit): stores 0 on the informed bit.
4. unsigned int invertBit (unsigned int x, int bit): toggles the bit value.
5. int testBit (unsigned int x, int bit): tests whether the bit is on or off. Actually, this function should just return the bit value as an integer.

2.4 Bit fields (partial words)

cor = cor & ~(0x3FF << 10) | (x << 10); // & tem precedência sobre | e ~, ~ tem precedência sobre ambos
int y = cor & 0x3FF;
int z = (cor >> 20) & 0x3FF;

struct Cor {
  // Pode especificar bits até o tamanho de um int
  // É transparente para o usuário como serão efetivamente alocados os campos
  unsigned int red: 10;    // 10 bits para red
  unsigned int green: 10;  // 10 bits para green
  unsigned int blue: 10;   // 10 bits para blue
};

...
Cor cor;
cor.green = 100;
cor.red = 900;
cor.blue = 320;