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”
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
#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;
}
Bit shifting
int
var = 3;
var <<= 1;
So the 3
0011
recv left shift
0110
int
var = 100;
var >>= 2;
remove last two digits
11001
Bit mask
x=26|19;
11010
| 10011
---------
11011 == 27
x=26&19;
11010
& 10011
---------
10010 == 18
NOT
x=~26;
11010
flip
00101
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:
x=26^19;
11010
^ 10011
---------
01001 == 9
So 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
// 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 )
// 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;
}
3>
// 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);
}
2>2>2>3>1>