A mágia dos bits
Antes de entender a magia dos bits vamos ver algo leve, claro em
linguagem C , bem como dar uma introdução ao entendimento de bits
e seu funcionamento em variáveis.
Uma variável do tipo “int” tem 4bytes ou seja 32bits
se você faz:
1
"int var = 3;"
Então temos:
4bytes = 32bits
cada octeto é um byte
“…00000000 00000000 00000011″
cada casa de número binário contamos como um bit
bit nada mais é que mnemônico para “Binary digiT”
Para saber número de bytes de uma variável usamos operador “sizeof(var)”
que nos retorna o valor em bytes da variável.
Se desejamos saber valor binário de um número fazemos divisão por 2
e enquanto o resto da divisão for diferente de “1″ fazemos a divisão
no final pegamos os restos ao contrário para ser o resultado final
número 12 para binário logo:
1
2
3
4
5
6
7
12 | 2
12 +------ 1100 <-- resultado ao contrário
0 6 | 2 -------------
+-----
0 3 | 2
+-----
1 1
Resultado 1100,repare que só temos um nibble ou seja um semiocteto
metade de 1 byte ou seja 4bits, lembra 1byte é 8 bits.
façamos então um programa para automatizar a tarefa de converter
decimal para binário
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
int main()
{
int bin[8],num=0,counter=0;
puts("Dec2Bin\n digite um numero");
scanf("%d",&num);
//para somente quando a divisão der "1"
while(num!=1)
{
//pegamos o resto da divisão ou se tiver um resultado é 1 se não é 0
bin[counter]=(num%2)?1:0;
//dividimos num por 2 e armazenamos em num para pegar o próximo resto
num/=2;
counter++;
}
bin[counter]=num;
//mostramos o array ao contrário
printf("\nResultado: ");
while(counter!=-1)
{
printf("%d",bin[counter]);
counter--;
}
printf("\n");
return 0;
}
continuando, tem outra forma melhor de se fazer isso, mas não
é hora de abordar isso agora.
Introdução Escovação de Bits “BitWise”
=======================================
Quando dizemos escovação de bits é uma mera referência ao trabalho
de manipular bits para se obter certos resultados. pessoal que trabalha
com microcontrolador seja AVR,PIC por muitas vezes tem que fazer tal
manipulação. Quando queremos desempenho escovação de bits pode nos
ajudar também embora o compilador já otimize muitas das tarefas.Outra
utilização é em tratamento de imagens e manipulação das mesmas,OpenCV
mesmo obriga você usar sempre que não existe uma solução pronta…
Bit Shifting “deslocamento de bit”
======================================
Deslocar um bit nada mais é que mudar o bit da sua posição original
para se chegar num certo resultado,chamamos esta técnica de bit shift
é um mnemônico do assembly “shl,shr“(shifiting left,shifiting right),
vamos a um exemplo de deslocamento para esquerda:
1
2
3
4
5
6
7
8
9
10
int var = 3;
var <<= 1;
o nosso 3
0011
recebeu um deslocamento para esquerda
0110
resultou em “6″, pode dar uma ilusão de aritmética de produto ou de
adição por ele mesmo, mas foi o resultado do deslocamento, forma
matemática correta segundo o livro do K&R para explanar nossa expressão
do exemplo seria “2*3¹“.
agora vamos ver deslocamento para direita:
1
2
3
4
5
6
7
8
9
int var = 100;
temos então 1100100
var >>= 2;
removemos os dois últimos digitos
11001
nos resulta “25″,forma matemática para tal é a seguinte “(100/2)²”
você me diz 25mil, cadê os zeros ? como disse remove os dois últimos
dígitos.
Mascaramento de Bit
======================
OR
—
Vamos ao operador “|” tem o mnemonico “OR” em assembly, vamos entender seu impacto
1
2
3
4
5
6
x=26|19;
11010
| 10011
---------
11011 == 27
AND
—
Agora o “&” mnemônico com “AND” em assembly
1
2
3
4
5
6
x=26&19;
11010
& 10011
---------
10010 == 18
NOT
—
O “~” é mnemônico com “NOT” ou seja ele é uma negação, fazendo um efeito inverso
do seu valor carregado, ou seja onde está 1 fica zero e vice e versa.
1
2
3
4
5
x=~26;
11010
flip
00101
resultado seria -27, Como mas por que não 5 ? lembra que falei um “int” é
4 bytes equivale a 32bits, então
0000 0000 0001 1010
1111 1111 1110 0101
agora sim,eu fiz em nibble para não precisar escrever muito…
XOR
—
O “^” é mnemônico para o XOR
1
2
3
4
5
6
x=26^19;
11010
^ 10011
---------
01001 == 9
veja se a tabela ne ajuda
1
2
3
4
5
6
7
8
9
,---,---,--------,
| 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...
Escovando Bits
================
Vamos usar bitwise para obter “desempenho” vejamos
alguns códigos com bitwise
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// programa para verificar se é impar ou par
main(int argc,char *argv[]){printf("%s\x0a",(!((atoi(argv[1]))&1))?"Par":"impar");}
// Isso = "x&1" usa mesma lógica disso "x%2"
// se retornar 0 é por que o último num binário é ZERO ou seja PAR...
// Sempre que precisar verificar se um número é multiplo
// fazer
resto = num & (divisor - 1);
x = 122 % 6;
//forma mais rápida
x = 122 & (6 - 1);
/*
se quiser fazer casting de float para Int
invés de fazer Casting de Float para Int assim "x = int(3.142)",
faça assim "x=3.142>>0;", melhora desempenho em 10%
*/
//operações ternárias são rapidas mas bit a bit são mais</b>
//invés
i = x < 0 ? -x : x;
//faça
i = (x ^ (x >> 31)) - (x >> 31);
//Comparando dois inteiros
x = a * b > 0;
//melhor forma
x = a ^ b >= 0;
//Comparar duas variáveis ver qual é a maior e menor
gamma = y ^ ((x ^ y) & -(x < y)); // gamma=menor(x, y)
gamma = x ^ ((x ^ y) & -(x < y)); // gamma=maior(x, y)
//Determinar se um inteiro é uma potência de 2
x = v && !(v & (v - 1));
//vai retornar verdadeiro ou falso <img src="http://botecounix.com.br/wp-includes/images/smilies/icon_wink.gif" alt="" class="wp-smiley">
//média para int
int a=6,b=8; printf("%d\n",((a&b)+(a^b)>>1));
//verificar se a posição "n" em bit é "1"
if( n & 1 << i )
lembra do nosso código simples de converter decimal para binário
vamos fazer um usando escovação de bits
1
2
3
4
5
6
7
8
9
10
11
12
// retirado da header beer.h Apenas usuários registrados e ativados podem ver os links., Clique aqui para se cadastrar...
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;
}
calcular raiz quadrada escovando bit por que não…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// retirado da header beer.h Apenas usuários registrados e ativados podem ver os links., Clique aqui para se cadastrar...
int bit_sqrt(int num)
{
//so 32 is sizeof(int)<<3
int num0=num,result=0,tbit=1<<((sizeof(int)<<3)-2);
if(num<=0)
{
printf("error bit_sqrt(), num = %d ",num);
return -1;
}
while(tbit>num0)
tbit>>=2;
while(tbit^0)
{
if(num0>=result+tbit)
{
num0-=result+tbit;
result=(result>>1)+tbit;
}else
result>>=1;
tbit>>=2;
}
return result;
}
não se compara esta função a de APIs como GMP,OpenSSL
mesmo por que é uma função simples muito menos a “math.h“,
foi mais para ilustrar.
posso usar bitwise em strings ?
se for um ponteiro por que não
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 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;
}
O assunto é gigante, então, sugiro que leiam mais sobre o assunto.
Contato: Movi3r@live.com
Twitter: @Movi3r
Antes de entender a magia dos bits vamos ver algo leve, claro em
linguagem C , bem como dar uma introdução ao entendimento de bits
e seu funcionamento em variáveis.
Uma variável do tipo “int” tem 4bytes ou seja 32bits
se você faz:
1
"int var = 3;"
Então temos:
4bytes = 32bits
cada octeto é um byte
“…00000000 00000000 00000011″
cada casa de número binário contamos como um bit
bit nada mais é que mnemônico para “Binary digiT”
Para saber número de bytes de uma variável usamos operador “sizeof(var)”
que nos retorna o valor em bytes da variável.
Se desejamos saber valor binário de um número fazemos divisão por 2
e enquanto o resto da divisão for diferente de “1″ fazemos a divisão
no final pegamos os restos ao contrário para ser o resultado final
número 12 para binário logo:
1
2
3
4
5
6
7
12 | 2
12 +------ 1100 <-- resultado ao contrário
0 6 | 2 -------------
+-----
0 3 | 2
+-----
1 1
Resultado 1100,repare que só temos um nibble ou seja um semiocteto
metade de 1 byte ou seja 4bits, lembra 1byte é 8 bits.
façamos então um programa para automatizar a tarefa de converter
decimal para binário
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
int main()
{
int bin[8],num=0,counter=0;
puts("Dec2Bin\n digite um numero");
scanf("%d",&num);
//para somente quando a divisão der "1"
while(num!=1)
{
//pegamos o resto da divisão ou se tiver um resultado é 1 se não é 0
bin[counter]=(num%2)?1:0;
//dividimos num por 2 e armazenamos em num para pegar o próximo resto
num/=2;
counter++;
}
bin[counter]=num;
//mostramos o array ao contrário
printf("\nResultado: ");
while(counter!=-1)
{
printf("%d",bin[counter]);
counter--;
}
printf("\n");
return 0;
}
continuando, tem outra forma melhor de se fazer isso, mas não
é hora de abordar isso agora.
Introdução Escovação de Bits “BitWise”
=======================================
Quando dizemos escovação de bits é uma mera referência ao trabalho
de manipular bits para se obter certos resultados. pessoal que trabalha
com microcontrolador seja AVR,PIC por muitas vezes tem que fazer tal
manipulação. Quando queremos desempenho escovação de bits pode nos
ajudar também embora o compilador já otimize muitas das tarefas.Outra
utilização é em tratamento de imagens e manipulação das mesmas,OpenCV
mesmo obriga você usar sempre que não existe uma solução pronta…
Bit Shifting “deslocamento de bit”
======================================
Deslocar um bit nada mais é que mudar o bit da sua posição original
para se chegar num certo resultado,chamamos esta técnica de bit shift
é um mnemônico do assembly “shl,shr“(shifiting left,shifiting right),
vamos a um exemplo de deslocamento para esquerda:
1
2
3
4
5
6
7
8
9
10
int var = 3;
var <<= 1;
o nosso 3
0011
recebeu um deslocamento para esquerda
0110
resultou em “6″, pode dar uma ilusão de aritmética de produto ou de
adição por ele mesmo, mas foi o resultado do deslocamento, forma
matemática correta segundo o livro do K&R para explanar nossa expressão
do exemplo seria “2*3¹“.
agora vamos ver deslocamento para direita:
1
2
3
4
5
6
7
8
9
int var = 100;
temos então 1100100
var >>= 2;
removemos os dois últimos digitos
11001
nos resulta “25″,forma matemática para tal é a seguinte “(100/2)²”
você me diz 25mil, cadê os zeros ? como disse remove os dois últimos
dígitos.
Mascaramento de Bit
======================
OR
—
Vamos ao operador “|” tem o mnemonico “OR” em assembly, vamos entender seu impacto
1
2
3
4
5
6
x=26|19;
11010
| 10011
---------
11011 == 27
AND
—
Agora o “&” mnemônico com “AND” em assembly
1
2
3
4
5
6
x=26&19;
11010
& 10011
---------
10010 == 18
NOT
—
O “~” é mnemônico com “NOT” ou seja ele é uma negação, fazendo um efeito inverso
do seu valor carregado, ou seja onde está 1 fica zero e vice e versa.
1
2
3
4
5
x=~26;
11010
flip
00101
resultado seria -27, Como mas por que não 5 ? lembra que falei um “int” é
4 bytes equivale a 32bits, então
0000 0000 0001 1010
1111 1111 1110 0101
agora sim,eu fiz em nibble para não precisar escrever muito…
XOR
—
O “^” é mnemônico para o XOR
1
2
3
4
5
6
x=26^19;
11010
^ 10011
---------
01001 == 9
veja se a tabela ne ajuda
1
2
3
4
5
6
7
8
9
,---,---,--------,
| 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...
Escovando Bits
================
Vamos usar bitwise para obter “desempenho” vejamos
alguns códigos com bitwise
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// programa para verificar se é impar ou par
main(int argc,char *argv[]){printf("%s\x0a",(!((atoi(argv[1]))&1))?"Par":"impar");}
// Isso = "x&1" usa mesma lógica disso "x%2"
// se retornar 0 é por que o último num binário é ZERO ou seja PAR...
// Sempre que precisar verificar se um número é multiplo
// fazer
resto = num & (divisor - 1);
x = 122 % 6;
//forma mais rápida
x = 122 & (6 - 1);
/*
se quiser fazer casting de float para Int
invés de fazer Casting de Float para Int assim "x = int(3.142)",
faça assim "x=3.142>>0;", melhora desempenho em 10%
*/
//operações ternárias são rapidas mas bit a bit são mais</b>
//invés
i = x < 0 ? -x : x;
//faça
i = (x ^ (x >> 31)) - (x >> 31);
//Comparando dois inteiros
x = a * b > 0;
//melhor forma
x = a ^ b >= 0;
//Comparar duas variáveis ver qual é a maior e menor
gamma = y ^ ((x ^ y) & -(x < y)); // gamma=menor(x, y)
gamma = x ^ ((x ^ y) & -(x < y)); // gamma=maior(x, y)
//Determinar se um inteiro é uma potência de 2
x = v && !(v & (v - 1));
//vai retornar verdadeiro ou falso <img src="http://botecounix.com.br/wp-includes/images/smilies/icon_wink.gif" alt="" class="wp-smiley">
//média para int
int a=6,b=8; printf("%d\n",((a&b)+(a^b)>>1));
//verificar se a posição "n" em bit é "1"
if( n & 1 << i )
lembra do nosso código simples de converter decimal para binário
vamos fazer um usando escovação de bits
1
2
3
4
5
6
7
8
9
10
11
12
// retirado da header beer.h Apenas usuários registrados e ativados podem ver os links., Clique aqui para se cadastrar...
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;
}
calcular raiz quadrada escovando bit por que não…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// retirado da header beer.h Apenas usuários registrados e ativados podem ver os links., Clique aqui para se cadastrar...
int bit_sqrt(int num)
{
//so 32 is sizeof(int)<<3
int num0=num,result=0,tbit=1<<((sizeof(int)<<3)-2);
if(num<=0)
{
printf("error bit_sqrt(), num = %d ",num);
return -1;
}
while(tbit>num0)
tbit>>=2;
while(tbit^0)
{
if(num0>=result+tbit)
{
num0-=result+tbit;
result=(result>>1)+tbit;
}else
result>>=1;
tbit>>=2;
}
return result;
}
não se compara esta função a de APIs como GMP,OpenSSL
mesmo por que é uma função simples muito menos a “math.h“,
foi mais para ilustrar.
posso usar bitwise em strings ?
se for um ponteiro por que não
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 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;
}
O assunto é gigante, então, sugiro que leiam mais sobre o assunto.
Contato: Movi3r@live.com
Twitter: @Movi3r
Comment