Big bit tips and tricks…
Manipulate bits is an amazing way to solve a lot of problems, but sometimes we don’t use this powerful tool in our problems either because require to think in very specific application or because a very tiny mistake could lead into a catastrophic error in the expected solution.
That’s why in this opportunity I would like to share with you some tips and tricks that you may or not know or maybe it could help you to refresh them.
But before that let’s to review some concepts just for the sake of completeness.
Bit manipulation is the process of applying logical operations on a sequence of bits to achieve a required result.
First of all, we need to be aware of the basic operators:
- & (and)
- | (or)
- ^ (xor)
- ~ (not)
- >> (right shift)
- << (left shift)
&
It’s only true if both are true.
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
|
It’s true if any of the inputs is true
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
^
It’s true in case of odd numbers
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
~
Flips the input
~ 0 = 1
~ 1 = 0
Right shift
divides by two
Left shift
multiplies by two
Bit Facts
x ^ 0s = x
x ^ 1s = ~x
x ^ x = 0x & 0s = 0
x & 1s = x
x & x = xx | 0s = x
x | 1s = 1
x | x = xx ^ 0 = x
x ^ 1 = x
x ^ x = 0Keep in mind that bit-wise operation help to make your programs faster (No so much) but it contributes its grain of sand.
Well, time to move forward…
1. Use AND (&) operator to check even or odd number
We usually use division and modulo to check if a number is odd or even. This can be also accomplished by using the AND operator. The last bit of a number is which determines if a number is odd or even (10 → 00001010), so we can use 1 (00000001) as mask (This can be also done with 0 and other operators, now you have a task).
00001010 &
00000001
— — — — —
00000000
#include <stdio.h>
int main()
{
int num1 = 10, num2 = 21;
// Check even odd
if (num1 & 1)
printf("%d is an ODD number.\n", num1);
else
printf("%d is an EVEN number.\n", num1);
if(num2 & 1)
printf("%d is an ODD number.\n", num2);
else
printf("%d is an EVEN number.\n", num2);
return 0;
}output:
10 is an EVEN number.
21 is an ODD number.2. Store multiple flags in a single variable
We usually use boolean flags variables in our solutions, for example: isEven, isMarried, isGoal_of_yepes (Well, this not), etc.
Suppose a case where you need to use several boolean flags variables, so maybe your first approach would be to create several 4 bytes integers, but in this case the amount of space will be n*4 bytes. What if we could use a single variable to accomplish that?. If fact, it is possible:
You can use bit masking to store multiple flag values in a single variable. A 4 byte unsigned integer can store 32 flags.
We use bitwise OR | operator to set flag. To unset or check flag status we use bitwise AND & operator. At a high level it is known as bit masking, but you can think it as set, unset and check a bit status.
#include <stdio.h>
int main()
{
// Make all bits off.
unsigned char flag = 0;
// Set marital status YES, i.e. 0th bit 1
// (flag => 0000 0001 = 1)
flag = flag | 1;
// Set voting status YES, i.e. 1st bit 1
// (flag => 0000 0011 = 3)
flag = flag | 2;
// Set VISA eligibility status YES, i.e. 2nd bit 1
// (flag => 0000 0111 = 7)
flag = flag | 4;
// Set Goal_of_yepes status YES, .i.e. 3th bit 1
// (flag => 000 1111 = 15)
flag = flag | 8; // Print flag value
printf("flag, DECIMAL = %d, HEX = %x\n\n", flag, flag);
// Check if married
if(flag & 1)
printf("You are married.\n");
else
printf("You are not married.\n");
// Check voting eligibility
if(flag & 2)
printf("You are eligible for voting.\n");
else
printf("You are not eligible for voting.\n");
// Check VISA status
if(flag & 4)
printf("You are eligible to get VISA.\n");
else
printf("You are not eligible to get VISA.\n");
if (flag & 8)
printf("It was Yepes' goal. \n");// Unset or set all flags to false.
flag = flag & (~(1 << 0));
flag = flag & (~(1 << 1));
flag = flag & (~(1 << 2));
flag = flag & (~(1 << 3));
// Print flag value
printf("\nflag, DECIMAL = %d, HEX = %x\n", flag, flag);
return 0;
}
output:
flag, DECIMAL = 7, HEX = 7
You are married.
You are eligible for voting.
You are eligible to get VISA.
It was Yepes' goal.flag, DECIMAL = 0, HEX = 0
3. Quickly convert character to lowercase and uppercase.
The common way to convert characters to lowercase or uppercase is using the ASCII code but bit operation also provides a way to do it.
You can use bitwise OR and AND operator to convert a character to lowercase and uppercase respectively.
To convert a character ch to lowercase use ch = ch | ' '. Whether ch is uppercase or lowercase. Result of this is always a lowercase character.
To convert a character ch to uppercase use ch = ch & '_'. It always return uppercase character, doesn't matter whether ch is uppercase or lowercase.
A -> 01000001 a -> 01100001
B -> 01000010 b -> 01100010
C -> 01000011 c -> 01100011
. .
. .
Z -> 01011010 z -> 01111010As we can see if we clear 5th bit of lower case characters, it will be converted into upper case character. We have to prepare a mask having 5th bit 0 and other 1 (10111111). This mask is bit representation of underscore character (‘_‘). The character ‘ch’ then AND with mask.
Example-
ch = ‘a’ (01100001)
mask = ‘_ ‘ (11011111)
ch & mask = ‘A’ (01000001)
The same logic apply to convert to lowercase.
#include <stdio.h>
int main()
{
// Convert to lowercase
printf("'a' ==> '%c'\n", ('a' | ' '));
printf("'A' ==> '%c'\n", ('A' | ' '));
// Convert to uppercase
printf("'a' ==> '%c'\n", ('a' & '_'));
printf("'A' ==> '%c'\n", ('a' & '_'));
return 0;
}output:
'a' ==> 'a'
'A' ==> 'a'
'a' ==> 'A'
'A' ==> 'A'4.Quick conditional assignment hack
What if a tell you that you can use a single line to represent the following block:
if (x == a)
x = b;
if (x == b)
x = a;You can use bitwise XOR operator for these type of assignments:
#include <stdio.h>
int main()
{
int a = 10, b = 20, x;
// Original value
x = a;
printf("x = %d\n", x);
// if (x == a) x = b;
x = a ^ b ^ x;
printf("x = %d\n", x);
// if (x == b) x = a;
x = a ^ b ^ x;
printf("x = %d\n", x);
// x = 0
x = x ^ x;
printf("x = %d\n", x);
return 0;
}Output:x = 10
x = 20
x = 10
x = 0
5.Find maximum or minimum without if…else
A common task when we are solving problems is to find a maximum or minimum and a common approach to use if…else to do it.
Let’s try it using bits:
#include <stdio.h>
int main()
{
int x = 10, y = 20;
int min = (y ^ (x ^ y) & -(x < y));
int max = (x ^ (x ^ y) & -(x < y));
printf("Minimum(10, 20) => %d\n", min);
printf("Maximum(10, 20) => %d\n", max);
return 0;Output:
}
Maximum(10, 20) => 20
Minimum(10, 20) => 106.Use bitwise XOR (^) operator to quickly swap two number without third variable
One of the first things that amazed me about Python when I started with it was that I could swap to variables values because of the tuple data structure definition in this language without using a third variable (This a common problem in interview questions).
Let’s do the same in C using our amazing tool:
#include <stdio.h>
int main()
{
int a, b;
// Input two numbers
printf("Enter two numbers to swap: ");
scanf("%d%d", &a, &b);
// Print original values.
printf("Original value: a=%d, b=%d\n", a, b);
// Swap a with b
a ^= b;
b ^= a;
a ^= b;
// Swapped values.
printf("Swapped value: a=%d, b=%d\n", a, b);
return 0;
}
Output:Enter two numbers to swap: 10 20
Original value: a=10, b=20
Swapped value: a=20, b=10
7. Increment by 1 (num + 1)
Maybe this trick will not be so handy, but it’s good keep in mind if some day you find it in a code:
Let’s increment by one using bit manipulation:
#include<stdio.h>
int main()
{
int num = 16;
num = -~num;
printf("num = %d", num);
return 0;
}8. Decrement by 1 (num — 1)
Decrement is very similar to increment, we just have to change the order of the signs:
#include<stdio.h>
int main()
{
int num = 16;
num = ~-num;
printf("num = %d", num);
return 0;
}I hope that with this article you realize how useful and beautiful is working with bit operations and that you start to use them in your problems. I am open to any suggestion.
Some useful resources:
