The magic of bits "Bitwise"
Introduction to bitwise
Art by Kev Walker

The story tale

Before the long tale to the course of magic bits, let's gonna for a little walk in the world of C language. Variable of type int has 4 bytes, so 32bits. If you do it:
"int var = 3;"
You can see this schema:
4bytes = 32bits
Looking to this context, each octet is a byte, half an octet can be called a nibble.
β€œβ€¦00000000 00000000 00000011”
Each place of binary number counts as one bit. The bit is nothing but a mnemonic for β€œBinary digiT”. So to know the number of bytes, we use the β€œsizeof(var)” operator, which returns the value in bytes of the variable. If we want to know the binary value of a number, we divide by 2 and as long as the remainder of the division is different from β€œ1”, we divide the end. We take the leftovers in reverse to be the final result, for example number 12:
12 | 2
12 +------ 1100 --> reverse result
0 6 | 2 -------------
+-----
0 3 | 2
+-----
1 1
Going on, there's another better way to do it, but no it's time to address this now.
#include <stdio.h>
int main()
{
int bin[8],num=0,counter=0;
puts("Dec2Bin\n digite um numero");
scanf("%d",&num);
while(num!=1)
{
​
bin[counter]=(num%2)?1:0;
​
num/=2;
counter++;
}
bin[counter]=num;
printf("\nResultado: ");
while(counter!=-1)
{
printf("%d",bin[counter]);
counter--;
}
printf("\n");
return 0;
}
Introduction to "Bitwise" When we say bitwise, it is a mere reference to work to manipulate bits to get specific results. Staff who work with microcontrollers, AVR and PIC often have to do such manipulation. When we want bitwise performance, we can also help, although the compiler already optimizes many tasks. Another use is in image processing and manipulation. OpenCV even forces you to use it whenever there is no ready-made solution.
Shifting a bit is nothing more than changing the bit from its original position. to get a specific result, we call this technique bit shift a mnemonic of the assembly β€œshl”(shifting left) and shr(shifting right), Let's look at an example of shifting to the left:
int var = 3;
var <<= 1;
So the 3
0011
recv left shift
0110
The result is β€œ6”, which can give an illusion of product arithmetic or addition by itself, but it was the result of displacement, form correctly according to the K&R math textbook to explain our expression an example would be β€œ2*3¹”.
Now look that following a shift to the right:
int var = 100;
So you can see 1100100
var >>= 2;
remove last two digits
11001
The result gives us β€œ25” the mathematical form for this is the following β€œ(100/2)²”.
You tell me 25 thousand. Where are the zeros? As I said, remove the last two digits.

Bit mask

OR
Let's go to the β€œ|” operator with the β€œOR” mnemonic in assembly. Let's go to understand its impact.
x=26|19;
11010
| 10011
---------
11011 == 27
AND
Now the β€œ&” mnemonic with β€œAND” in assembly.
x=26&19;
11010
& 10011
---------
10010 == 18
The "~" is mnemonic with "NOT"; that is, it is a negation, making an inverse effect of its loaded value, where one is, it becomes zero and vice versa. So the result would be -27, Like but why not 5? remember that I said an "int" is 4 bytes equals 32bits, so look at the following:
0000 0000 0001 1010
1111 1111 1110 0101
I did it in a nibble, so I don't have to write too much.
XOR
The β€œ^” is a mnemonic for XOR.
x=26^19;
11010
^ 10011
---------
01001 == 9
So look at that table in the following:
,---,---,--------,
| a | b | a ^ b | in this point you can make SWAP
|---|---|--------| example:
| 0 | 0 | 0 |
| 0 | 1 | 1 | int A=4,B=7;
| 1 | 0 | 1 | A^=B; B^=A; A^=B;
| 1 | 1 | 0 |
'---'---'-------cc
​

The magic of the bits

Let's use bitwise to get "performance" let's go to get
some bitwise code snips.
// one line to check if a value is even or odd
main(int argc,char *argv[]){printf("%s\x0a",(!((atoi(argv[1]))&1))?"odd":"even");}
// This "x&1" same effect like "x%2"
// num is multiple
resto = num & (divisor - 1);
x = 122 % 6;
// maybe faster
x = 122 & (6 - 1);
/*
casting float to Int
"x = int(3.142)" try to "x=3.142>>0;" can be improve the performance
*/
// ternary operation
i = x < 0 ? -x : x;
// try
i = (x ^ (x >> 31)) - (x >> 31);
// compare ints
x = a * b > 0;
// or try
x = a ^ b >= 0;
//Compare two vars
gamma = y ^ ((x ^ y) & -(x < y)); // equivalent to gamma=menor(x, y)
gamma = x ^ ((x ^ y) & -(x < y)); // equivalent to gamma=maior(x, y)
//check 2 potence
x = v && !(v & (v - 1));
​
//average number to integer
int a=6,b=8; printf("%d\n",((a&b)+(a^b)>>1));
// check if exist position "n" in bit "1"
if( n & 1 << i )
So remember our simple code to convert decimal to binary? Let's make one using bitwise πŸ™‚
// https://github.com/CoolerVoid/C/
char * dec2bin(int n, char * string)
{
int i;
static int size = 8 * sizeof(int);
for(i = size - 1; i >= 0; i--, n >>= 1)
string[i] = (01 & n) + '0';
string[size] = '\0';
return string;
}
The square root calc, following bitwise path:
// header beer.h https://github.com/CoolerVoid/C/edit/master/beer.h
int bit_sqrt(int num)
{
//so 32 is sizeof(int)<<3 -1="" bit_sqrt="" error="" if="" int="" num0="num,result=0,tbit=1<<((sizeof(int)<<3)-2);" num="" printf="" return="" tbit="" while="">num0)
tbit>>=2;
while(tbit^0)
{
if(num0>=result+tbit)
{
num0-=result+tbit;
result=(result>>1)+tbit;
}else
result>>=1;
tbit>>=2;
}
return result;
}
This function cannot be compared to APIs such as GMP and OpenSSL even because it is a simple function, much less β€œmath.h” it was more to illustrate.

Can I use bitwise on strings?

If it is a pointer, why not?
// return reverse string
char *strrev(char *str)
{
char *p1, *p2;
if(! str || ! *str)
return str;
for(p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
{
*p1 ^= *p2;
*p2 ^= *p1;
*p1 ^= *p2;
}
return str;
}
So this second example is a simple benchmark following CPU cycles to compare arithmetic division using bitwise and common resources.
/*
Author: Cooler_
Contact: coolerlair[at]gmail[dot]com
​
Compares arithmetic division with bitwise and without
test CPU cycles and soon
​
$ gcc -o code code.c; ./code
*/
#include <stdio.h>
#include <stdlib.h>
#include <x86intrin.h>
#include <cpuid.h>
#include <inttypes.h>
#define LAST "\033[0m"
#define RED "\033[22;31m"
void mul()
{
int x=50,y=0;
while(x)
{
y=x*2;
x--;
}
}
void leftshift()
{
register int x=50,y=0;
while(x)
{
y=x<<1 bit_div7="" div7="" n="" num="" register="" return="" unsigned="" x--="" x="(num" y="">>1)+(num>>4);
x+=x>>6;
x+=(x>>12)+(x>>24);
x>>=2;
y=num-((x<<3 return="" x="" y="">>3);
}
unsigned div3(unsigned n)
{
return n/3;
}
//
unsigned bit_div3(unsigned num)
{
register unsigned x,y;
x=(num>>2)+(num>>4);
x+=x>>4;
x+=x>>8;
x+=x>>16;
y=num-((x<<2 ficou="" return="" ruim="" x="" y="">>5);
// ruim return x+( (y+5+(y<<2>>4);
return x+( (((y+1)<<2 y="">>4);
}
int main(void)
{
int x=0;
uint32_t a=0, b=0, c=0, d=0;
register uint64_t y=0;
x = 0;
do {
__cpuid(0, a, b, c, d);
y = _rdtsc();
leftshift();
y = _rdtsc() - y;
} while (++x < 2);
printf("::: left shift: %s %lld %s cicles\n",RED, y,LAST);
x = 0;
do {
__cpuid(0, a, b, c, d);
y = _rdtsc();
mul();
y = _rdtsc() - y;
} while (++x < 2);
printf("::: mul: %s %lld %s cicles\n", RED,y,LAST);
unsigned int z=0;
x = 0;
do {
__cpuid(0, a, b, c, d);
y = _rdtsc();
z=div7(560000*x);
printf("result: %d\n",z);
y = _rdtsc() - y;
} while (++x < 2);
printf("::: div7: %s %lld %s cicles\n", RED,y,LAST);
z=0;
x = 0;
do {
__cpuid(0, a, b, c, d);
y = _rdtsc();
z=bit_div7(560000*x);
printf("result: %d\n",z);
y = _rdtsc() - y;
} while (++x < 2);
printf("::: bit_div7: %s %lld %s cicles\n",RED, y,LAST);
x = 0;
do {
__cpuid(0, a, b, c, d);
y = _rdtsc();
z=div3(560000*x);
printf("result: %d\n",z);
y = _rdtsc() - y;
} while (++x < 2);
printf("::: div3: %s %lld %s cicles\n",RED, y,LAST);
z=0;
x = 0;
do {
__cpuid(0, a, b, c, d);
y = _rdtsc();
z=bit_div3(560000*x);
printf("result: %d\n",z);
y = _rdtsc() - y;
} while (++x < 2);
printf("::: bit_div3: %s %lld %s cicles\n", RED,y,LAST);
exit(0);
}
This subject is huge. I'll stop here for the end. I suggest you read it to delve deeper into the subject by bitwise, the following book β€œhacker’s delight".
​

References

Hacker's Delight
Amazon.com
The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams
Amazon.com
Thank you for reading, cheers!