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:

Looking to this context, each octet is a byte, half an octet can be called a nibble.

Each place of binary number counts as one bit. The bit is nothing but a mnemonic for β**B**inary digi**T**β. 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:

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.

// 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".**

Hacker's Delight

Amazon.com

The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams

Amazon.com

Last modified 3d ago