Bit Hacking in C

17 Aug, 2025

In C we can oftentimes implement certain operation efficiently using bitwise manipulations.

We have the following set of bitwise manipulations:

& bitwise AND

| bitwise inclusive OR

^ bitwise exclusive OR

<< left shift

>> right shift

~ one's complement (unary)

Let's consider a few examples to get familiar with these operations. In all our examples, we will number bits from right to left, so bit 0 is the least significant bit. The parameter p will refer to the starting position of the bit-field from the right.

getbits(x, p, n)

The below function will get the n bits starting from position p.

/* getbits: get n bits from position p */
uint32_t getbits(uint32_t x, uint32_t p, uint32_t n) {
  uint32_t MASK = ~(~0 << n);
  uint32_t offset = p + 1 - n;
  return (x >> offset) & MASK;
}

That is because x >> (p+1-n) shifts the nth bit starting from p to the leftmost bit. ~(~0 << n) than masks out everything except the first n bits in the sequence.

For illustration let's see for p = 3, n = 2 how this works on an 8 bit sequence

(~0 << 2) =  11111100
~(~0 << 2) = 00000011

Assume x = 10101010

x >> (3+1-2) = x >> 2 = 00101010

AND the two

00000011
00101010
--------
00000010

We can verify that in the following way:

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

/* getbits: get n bits from position p */
uint32_t getbits(uint32_t x, uint32_t p, uint32_t n) {
  uint32_t MASK = ~(~0 << n);
  uint32_t offset = p + 1 - n;
  return (x >> offset) & MASK;
}

int main() {
  uint32_t x = 139;              // 10001011
  uint32_t z = getbits(x, 5, 3); // Becomes 001 = 1
  printf("%d\n", z);
}

setbits(x, y, p, n)

The below function will set the n bits starting from p in x to the leftmost n bits in y.

uint32_t setbits(uint32_t x, uint32_t y, uint32_t p, uint32_t n) {
  uint32_t offset = ((p + 1) - n);
  uint32_t MASK = (~(~0 << n)) << offset;
  return (~MASK & x) | (MASK & (y << offset));
}

The mask can be used to extract the n bits starting from p. Negating it will mask exactly these entries out. If you have problems visualising that write it down for a small example like i did above.

We extract the n bits starting from p from y shifted to the left. We shifted left here to align the leftmost bits to the appropriate position and than use the mask to mask everything except these out. We OR with x where the n bits starting from p are masked out to get the final result.

Note that we can write an equivalent version in terms of XOR using the fact that the above expression will give us

MASK = 0 -> x 
MASK = 1 -> y << offset

x ^ ((x ^ (y << offset)) & MASK)

will do exactly the same because

MASK = 0 -> x ^ 0 = x
MASK = 1 -> x ^ x ^ (y << offset) = y << offset

see the Truth table for the XOR operation if that doesn't make sense immediately.

We can verify this

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

uint32_t setbits(uint32_t x, uint32_t y, uint32_t p, uint32_t n) {
  uint32_t offset = ((p + 1) - n);
  uint32_t MASK = (~(~0 << n)) << offset;
  return x ^ (((x ^ (y << offset)) & MASK));
}

int main() {
  uint32_t x = 139;                 // 10001011
  uint32_t y = 3;                   // 11
  uint32_t z = setbits(x, y, 6, 2); // Becomes 11101011 = 235
  printf("%d\n", z);
}

invert(x,p,n)

The below function will invert the n bits starting from p.

For that first note that x ^ 1 = ~x and x ^ 0 = x. We can than simply XOR our expression x with the MASK from above and will get the inverse in the specified range. Where the mask is 0 our expression will stay invariant as desired.

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

uint32_t invert(uint32_t x, uint32_t p, uint32_t n) {
  uint32_t offset = ((p + 1) - n);
  uint32_t MASK = (~(~0 << n)) << offset;
  return x ^ MASK;
}

int main() {
  uint32_t x = 139;             // 10001011
  uint32_t y = invert(x, 6, 3); // Becomes 11111011 = 251
  printf("%d\n", y);
}

leftrot(x,n) & rightrot(x,n)

Ultimately we want to apply leftrot and rightrow to 32 bit expression. Let us analyse the 8 bit case however to make it easier understandable.

Consider

10001001

A rotation to the left by a factor of 2 gives

00100110

After thinking a little bit about it we can notice the following:

• A shift to the right by 8-n bits is the same as shifting to the left with wrap around by n bits and masking the leftmost 8-n bits out
• A shift to the left by n bits is the same as shifting to the left with wrap around by n bits and masking the rightmost n elements out. Using this we can combine the two with an OR and will get an expression that describes a shift to the left with wrap around. Similar we can derive the equation for rightrot. Of course the above analysis applies to sequences of 32 bits as well.

To see why the above two are true let's consider a small example for an 8 bit sequence:

10011011 >> 6
00000010 = shift by two with wrap around to the left and masking out the leftmost 6 elements

10011011 << 2
01101100 = shift by two with wrap around to the left and masking out the rightmost 2 elements.

In C this can be implemented as follows:

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

uint32_t leftrot(uint32_t x, uint32_t n) { return (x << n) | (x >> (32 - n)); }
uint32_t rightrot(uint32_t x, uint32_t n) { return (x >> n) | (x << (32 - n)); }

int main() {
  uint32_t x = 0b10000000000000000000000000000000;
  // Shift circular to left by 2 gives 2
  uint32_t y = leftrot(x, 2);
  printf("%u\n", y);
  x = 0b00000000000000000000000000000001;
  // Right circular to right by 2 gives 2^30 = 1073741824
  y = rightrot(x, 2);
  printf("%u\n", y);
}

Conclusion

I hope this blogpost serves as a good introduction to low level bit manipulations. If you like to exchange ideas I am happy to connect via my Linkedin.