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.
