Before the long tale to the course of magic bits, let's gonna for a little walk in the world of C language.
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”
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;
}
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.
Bit shifting
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
is a mnemonic of the assembly “shl,shr”(shifting left, shifting right),
Let's look at an example of shifting to the left:
int var = 3;var <<= 1;So the 3 0011recv left shift 0110The result is “6”, which can give an illusion of product arithmetic or
addition by itself, but it was the result of displacement, form
Correct 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 == 27AND
Now the “&” mnemonic with “AND” in assembly.
x=26&19; 11010& 10011--------- 10010 == 18NOT
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.
x=~26; 11010 flip 00101the 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 == 9So look at that table in the following:
,---,---,--------,| a | b | a ^ b | pode-se fazer SWAP sem usar uma terceira variável|---|---|--------| exemplo:| 0 | 0 | 0 || 0 | 1 | 1 | int A=4,B=7;| 1 | 0 | 1 | A^=B; B^=A; A^=B;| 1 | 1 | 0 | // "A" agora vale 7'---'---'--------' alguns usam XOR em criptografia também...The magic of the bits
Let's use bitwise to get "performance" let's go to get
some bitwise code snips.
// 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 cyles to compare arithmetic division using bitwise and common resource.
/*
Author: Cooler_
Contact: c00f3r[at]gmail[dot]com
Compares arithmetic division with bitwise and without...
test CPU cycles...
$ 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.”
