Tag: bitwise

Heh… fancy title, isn’t it?

Low-level programming always fascinated me, I can’t put in words the epiphany that I experienced when I first wrote a set of instructions to divide an integer.  Moreover, I always had an interest in performance optimization.

Here I present some tips used to improve performance or reduce memory usage. Keep in mind that today’s modern compilers are smart enough to perform better optimizations in some cases and some of the techniques presented here are in fact slower on modern CPU architectures due to instructions being executed in parallel.

I hope you already understand logic gates and bitwise operations. The input will be in a pseudo-code followed by the output and binary representation in another block.

Even or Odd

This method is faster than modulo operation as it doesn’t uses division.

bool isOdd(int num)
{
   return num&1;
}

isOdd(7) returns 1

  00000111 <- 7
& 00000001 <- 1
----------
  00000001 <- 1

Forcing evaluations in if/elseif statements

If you are using AND(&&) and OR(||) operators with functions/methods you know that if the first or any subsequent fails(in AND case) or succeeds(in OR case) the other methods won’t execute. To get around that you can use bitwise operators.

//consider the return of the functions as boolean(0/1) and not an arbitrary integer
if (myFunc1()&myFunc2()&myFunc3)
{
// all three executed and returned true
}
else
{
// all three executed and at lease one returned false
}

myFunc1() returns 1
myFunc2() returns 0
myFunc3() returns 1

  00000001 <- 1
& 00000000 <- 0
& 00000001 <- 1
----------
  00000000 <- 0

//If AND(&&) was used, the myFunc3() would never be performed. The same idea can be used with OR(||) and |, but to execute the subsequent ones in case of the first succeed.

XOR Swap

Swap values between two int variables without a third one. Not recommended on modern systems(but still amazing!).

char a=5;
char b=3;
a=a^b;
b=b^a;
a=a^b;

  00000101 <- a=5
^ 00000011 <- b=3
----------
  00000110 <- a=6

  00000011 <- b=3
^ 00000110 <- a=6
----------
  00000101 <- b=5

  00000110 <- a=6
^ 00000101 <- b=5
----------
  00000011 <- a=3

Division and multiplication by powers of two

With bitshift you can divide or multiply by any power of two.

Swap values between two int variables without a third one. Not recommended on modern systems(but still amazing!).

char a=5<<1; // 5*2 or 5*(2^1)
char b=2<<3; // 2*8 or 2*(2^3)
char c=80>>4; // 80/16 or 80/(2^4)

  00000101 <- 5
      << 1
----------
  00001010 <- a=10

  00000010 <- 2
      << 3
----------
  00010000 <- a=16

  01010000 <- 80
      >> 4
----------
  00000101 <- a=5

Extracting Red, Blue and Green from RGB

You can use bitshift and & to isolate colors.

uint32_t color = 0x9C5052;
char red=(color>>16)&0xFF;
char blue=(color>>8)&0xFF;
char green;color&0xFF;

   100111000101000001010010 <- 10244178 / 0x9C5052
                      >> 16
---------------------------
                   10011100
                  &11111111
---------------------------
                   10011100 <- 156 or 0x9C

   100111000101000001010010 <- 10244178 / 0x9C5052
                       >> 8
---------------------------
           1001110001010000
                  &11111111
---------------------------
                   01010000 <- 80 or 0x50

   100111000101000001010010 <- 10244178 / 0x9C5052
                  &11111111
---------------------------
                   01010010 <- 82 or 0x52

Checking, inverting, setting and clearing the nth bit

You can use bitshift and & to isolate colors.

char num = 57;
char bit = 6; / nth bit defined as 6
//checking 6th bit
return 1&(num>>(bit-1));
//inverting 6th bit
return num^(1<<(bit-1));
//setting 6th bit
return num|(1<<(bit-1));
//clearing 6th bit
return num&~(1<<(bit-1));

//checking
   00111001 // 57
       >> 5 // shift 5 times
-----------
   00000001 
&  00000001
-----------
   00000001 // 6th bit is on

//inverting
   00000001 // 1
       << 5 // shift 5 times
-----------
   00100000 
^  00111001 
-----------
   00011001

//setting
   00000001 // 1
       << 5 // shift 5 times
-----------
   00100000 
|  00111001 
-----------
   00111001

//clearing
   00000001 // 1
       << 5 // shift 5 times
-----------
~  00100000 // reverses the bits
-----------
   11011111 
&  00111001 
-----------
   00011001

Some programming languages allocate one byte for a boolean, you can use this technique to treat an integer as an array of booleans or flags.

Conclusion

These are my favorite hacks and utilities using bitwise operations. Be careful since your code can become confusing and unreadable for your coworkers.

You can see more complex examples here. But I don’t recommend you using too extreme and obscure for the reasons mentioned above.