Como usar campo de bit

joubet · 25 de fevereiro de 2007

Pela primeira vez não consegui entender sua resposta.

Nos x86 existem oito (7, duas são redundantes) instruções de deslocamento de bit, as duas primeiras letras definem a operação, a ultima a direção (l = left, r = right)
sal/sar = arithmetic shift, desloca os bits, preenche os espaços vazios a direita com 0, e a esquerda com o bit de sinal, o C executa essa instrução quando encontra os operadores << e >>, x << y é equivalente a x * (2 elevado a y) e x >> y é equivalente a x / (2 elevado a y), nos processadores de hoje essas instruções são muito mais rapidas que divisões e multiplicações,

ex (o segundo operador esta com representação decimal apenas para facilitar a leitura):

00100100 << 4 = 01000000

00100100 >> 4 = 00000100

10100100 >> 4 = 11110100

shl/shr = logical shift, desloca ....................

num primeiro momento, achei, que "shl/shr " fosse algum tipo de registrador, que os operadores de deslocameto atuassem, mas não tenho certeza, Poderia partir deste ponto para que eu possa começar a enrender, a cho que sua explicação, está num nível mais alto do que as minhas modestas perguntas.

Obrigado

EduardoS · 25 de fevereiro de 2007

shl/shr são as instruções que fazem o deslocamento ("shift left" e "shift right").

joubet · 27 de fevereiro de 2007

OK.

O programa da pergunta 3, seria:

#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

int main()
{
    int valor1 = 4;
    int valor2 = 5;

    char binario[8] = {'\0'};
    char binario2[20]={'\0'};
    char binario3[8]={'\0'};
    char binario4[20]={'\0'};

    printf("%i\n", valor1);  
    itoa(valor1, binario, 2); /* Converte um numero inteiro em string,
    e coloca a saida da string num formato entre as bases 2 e 16*/
    printf("%s\n", binario);

    printf("%i\n", valor2);
    itoa(valor2, binario, 2);
    printf("%s\n", binario);

    printf ("Deslocamento a esquerda de um bit\n");
    valor2 = valor2 << 1;/* Desloca binário de 1 a esquerda e está sendo
    multiplicado por 2*/
    itoa(valor2, binario, 2);
    printf("%s\n", binario);

    printf ("Deslocamento a direita de um bit\n");
    valor2 = valor2 >> 1;
    itoa(valor2, binario, 2);
    printf("%s\n", binario);

    printf ("Deslocamento a esquerda de dois bits\n");
    valor2 = valor2 << 2; /* Desloca binário de 2 a esqquerda multiplicado 4*/
    itoa(valor2, binario, 2);
    printf("%s\n", binario);

    itoa(~valor1, binario2, 2); /*complemento a um*/
    printf("Complemento a um:   %s\n", binario2);

    itoa(-valor1, binario2, 2);
    printf("Complemento a dois: %s\n", binario2);

    printf ("\nComparando os numeros 4 e 5\n");
    itoa(valor1 | valor2, binario4, 2);
     printf("\n\"Ou\" de campo de bit:   %s\n",binario4);

    system ("pause");
    return (0);
    }

Resultado do programa;

4
100

5

101

Deslocamento a esquerda de um bit

1010

Deslocamento a direita de um bit

101

Deslocamento a esquerda de dois bits

10100

Complemento a um: 11111111111111111111111111111011

Complemento a dois: 11111111111111111111111111111100

Comparando os numeros 4 e 5

"Ou" de campo de bit: 10100

Pressione qualquer tecla para continuar . . .

a) Observe, que o “OU” de bit, saiu com “00”, quando deveria sair apenas “101” qual o motivo ?

O deslocamento de bit, foi feito na variável “valor2”, sem menção as instruções que você citou (shl/shr, por ex:.) , isto foi que me causou estranheza. Poderia comentar ?

c) Este programa tem um exemplo simples de complemento a um e a dois. Poderia comentar sua apliocação.

Obrigado.

EduardoS · 27 de fevereiro de 2007

a) Observe, que o “OU” de bit, saiu com “00”, quando deveria sair apenas “101” qual o motivo ?

Algumas linhas antes você fez isso:


    printf ("Deslocamento a esquerda de dois bits\n");
    valor2 = valor2 << 2; /* Desloca binário de 2 a esqquerda multiplicado 4*/
    itoa(valor2, binario, 2);
    printf("%s\n", binario);

O que alterou o valor2 de 101 para 10100, esse novo valor2 "or" valor1 (que vale 100) da 10100 mesmo.

O deslocamento de bit, foi feito na variável “valor2”, sem menção as instruções que você citou (shl/shr, por ex:.) , isto foi que me causou estranheza. Poderia comentar ?

As instruções aparecem depois que o programa for compilado, para executar o operador "<<" o C usa a instrução shl, da mesma forma que para executar o operador "+" ele usa a instrução add.

c) Este programa tem um exemplo simples de complemento a um e a dois. Poderia comentar sua apliocação.

Complemento a dois = É o operador metemático de negação, ex: x = -z*y;

Complemento a um = Geralmente é usado junto com os demais operadores lógicos.

joubet · 28 de fevereiro de 2007

Confesso, que minha cabeça deve estar dura, pois não entendi a afirmativa

rol/ror = rotate, esse é o deslocamente de bits que você mencionou, não existe no C um operador que faça isso, ex
10110111 rol 3 = 10111101

No programa que botei como exemplo, foi feito com os bits deslocados ? não foram rotacionados considerando o tipo de dado (int), já que 0 (zero) à esquerda não aparece no vídeo ?

4
100

5

101

Deslocamento a esquerda de um bit

1010

Deslocamento a direita de um bit

101

Ok. entendi que complemento a dois, representa o sinal negativo na seqüência de bits, mas não entendi a afirmação:

Complemento a um = Geralmente é usado junto com os demais operadores lógicos.

Como assim ?

Obrigado.

EduardoS · 28 de fevereiro de 2007

rotates e shifts:

0101 << 1 = 1010

0101 >> 1 = 0010

0101 rol 1 = 1010

0101 ror 1 = 1010

Os bits em azul foram inseridos, e bits inseridos são sempre 0, os bits em verde "deram a volta", os bits em vermelho, foram descartados, jogados fora, os demais foram deslocados, no caso citei um exemplo que tem apenas 4 bits, mas tambem vale se tiver mais.

complemento a um

O código abaixo seleciona os bits que estão em x e em y;


z = x & y;

já o código abaixo seleciona os bits que estão em x mas não estão em y:


z = x & ~y;

joubet · 1 de março de 2007

Ok

.

Com base em sua resposta, devo concluir, que a linha de código abaixo(posta ao fim do programa):

itoa(valor1 & valor2, binario5,2);

colocara os bits das variáveis valor1 e valor2 na variável binário5, correto ?

Teve como resultado:

“&” de campo de bit: 100

só que estou achando o valor pequeno. Acho que tem algo .......

baseado em sua outra resposta inclui mais uma linha:

itoa(valor1 & ~valor2,binario6,2);

Teve como resultado:

“&” de campo de bit: 0

Considerando, que foram selecionados os bits de valor1, e não de valor2, é certo deduzir, que os bits de valor1 é realmente zero ? por que ? dá ideia que (~) funciona como uma forma de excluir bits hum.... acho que essa interpretação está errada.

Obrigado

EduardoS · 1 de março de 2007

Não...

valor1 = 0100

valor2 = 0101

valor1 & ~valor2 = 0

já o código abaixo seleciona os bits que estão em x mas não estão em y:

Olhando bit a bit a partir da esquerda:

O primeiro não esta no valor1, não serve;

O segundo esta no valor1, mas como tambem esta no valor2 não serve;

O terceiro e quarto são iguais ao primeiro;

O único caso que resultaria em 1 seria se o primeiro tivesse 1 e o segundo não.

joubet · 2 de março de 2007

Ok, entendi sua aritmética. Só que percebi, que a forma como fiz as perguntas iniciais, deu uma interpretação dúbia no seu Não. Fiquei na dúvida em que ponto minha interpretação estava realmente errada. Foi a dedução de que a variável “binario5” guarda nela os bits das variáveis “valor1” e “valor2” ? Se for esse o erro, o que binario5 guarda realmente ?

Obrigado

EduardoS · 3 de março de 2007

Li novamente o seu post, e acho que me confundi quando disse "Não..."

Ele se referia a sua ultima frase, estava em dúvida de qual interpretação você dizia estar errada.

joubet · 3 de março de 2007

Esse nosso último diálogo ficou truncado. vamos deixar isso para deepois. Considere:

1) Recebi de um colega, a seguinte tabela, e gostaria de saber, se está realmente certo.

Vamos tomar como exemplo: 4 e 5. Teremos respectivamente "100" e "101".
Operação '|':

Tabela:

0 | 0 = 0

0 | 1 = 1

1 | 0 = 1

1 | 1 = 1

Começando pelo bit menos significativo de cada número, ou seja pela direita:

100

101

0 | 1 = 1 (pela linha 2 da tabela)

Logo o resultado será xx1

Próximo:

100

101

0 | 0 = 0 (pela linha 1 da tabela)

Logo o resultado será x01

Próximo:

100

101

1 | 1 = 1 (pela linha 3 da tabela)

Logo o resultado será 101

Ou seja o número final em binário é 101 = 5

=====================================

Operação '&':

Tabela:

0 & 0 = 0

0 & 1 = 0

1 & 0 = 0

1 & 1 = 1

Começando pelo bit menos significativo de cada número, ou seja pela direita:

100

101

0 | 1 = 0 (pela linha 2 da tabela)

Logo o resultado será xx0

Próximo:

100

101

0 | 0 = 0 (pela linha 1 da tabela)

Logo o resultado será x01

Próximo:

100

101

1 | 1 = 1 (pela linha 3 da tabela)

Logo o resultado será 101

Ou seja o número final em binário é 100 = 4

=====================================

Operação '^':

Tabela:

0 ^ 0 = 0

0 ^ 1 = 1

1 ^ 0 = 1

1 ^ 1 = 0

Começando pelo bit menos significativo de cada número, ou seja pela direita:

100

101

0 | 1 = 1 (pela linha 2 da tabela)

Logo o resultado será xx1

Próximo:

100

101

0 | 0 = 0 (pela linha 1 da tabela)

Logo o resultado será x01

Próximo:

100

101

1 | 1 = 0 (pela linha 3 da tabela)

Logo o resultado será 001

Ou seja o número final em binário é 001= 1

=====================================

Tendo um dos números tiver mais dígitos que o outro, complete o que tiver menos digitos com zeros à esquerda.

Exemplo: 1 & 7 = 001 & 111 = 001.

2) relendo sua resposta, onde você diz :

Os bits inseridos são sempre zero, me pergunto, por que sempre zero ? não tem como inserir “uns” ?

3) Quando estávamos falando de instruções no post anterior, você citou “add”, creio que esta seja uma instrução equivalente para soma em assembly. Sei que a linguagem C (derivada do , foi criada, para otimizar, rotinas em assembly. Pergunto: tem como rodar ou usar comandos assembly no C ?

4) estamos discutindo campo de bit a um certo tempo, mas em que tipo de programa se usa campo de bit

5) Quis perguntar oseguinte: Quando faço:

itoa(valor1 & valor2, binario5,2);

Estou colocando todos os bits da variavel "valor1" e "valor2" na variável "binario5" ?

6) Qundo faço:

itoa(valor1 & ~valor2,binario6,2);

Considerando, que foram selecionados os bits de valor1, e não de valor2, é certo deduzir, que os bits de valor1 é realmente zero ? por que ? dá ideia que (~) funciona como uma forma de excluir os bits da variável "valor2". É isso meesmo ? acho que agora está mais claro.

Você tem experiência como docente ? suas explicações são bem didáticas.

Obrigado

EduardoS · 3 de março de 2007

1) Recebi de um colega, a seguinte tabela, e gostaria de saber, se está realmente certo.

A tabela esta certa, é isso mesmo.

2) relendo sua resposta, onde você diz :

Os bits inseridos são sempre zero, me pergunto, por que sempre zero ? não tem como inserir “uns” ?

É sempre 0 para ficar de acordo com a nossa matemática.

3) Quando estávamos falando de instruções no post anterior, você citou “add”, creio que esta seja uma instrução equivalente para soma em assembly. Sei que a linguagem C (derivada do , foi criada, para otimizar, rotinas em assembly. Pergunto: tem como rodar ou usar comandos assembly no C ?

Sim, mas depende do compilador e da arquitetura, o mais comum é o comando "asm{}" ou "__asm__{}"

4) estamos discutindo campo de bit a um certo tempo, mas em que tipo de programa se usa campo de bit

Vai da criatividade do programador, a utilização deles não é tão simples quanto as operações aritiméticas, mas podem ser uteis, a maioria dos algoritimos que usam bem essas operações é feita em assembly, converti um strLen feito em assembly para C que mostra alguns desses operadores, é 32bits e o compilador pode dar vários warnings, mas ignore-os:


int agnerStrLen(char* str)
{
    int* tmp = (int*)((int) str & -4);
    int durty = -1 << (((int) str - (int) tmp) << 3);
    unsigned int res = 0;
    int ret = 0;
    if(!(res = (0x80808080 & durty & ~(*tmp) & (*tmp - 0x01010101))))
        do{tmp++;}while(!(res = (0x80808080 & ~(*tmp) & (*tmp - 0x01010101))));
    ret = (int) tmp - (int) str;
    if(!(res & 0x8080))
    {
        res >>= 16;
        ret += 2;
    }
    if(!(res & 0x80))
        ret += 1;
    return ret;
}

5) Quis perguntar oseguinte: Quando faço:
itoa(valor1 & valor2, binario5,2);
Estou colocando todos os bits da variavel "valor1" e "valor2" na variável "binario5" ?

A rigor você esta convertendo o resultado de "valor1 & valor2" para ascii na base 2...

Simplificando você esta jogando o resultado de "valor1 & valor2" na variável binário5.

6) Qundo faço:
itoa(valor1 & ~valor2,binario6,2);
Considerando, que foram selecionados os bits de valor1, e não de valor2, é certo deduzir, que os bits de valor1 é realmente zero ? por que ? dá ideia que (~) funciona como uma forma de excluir os bits da variável "valor2". É isso meesmo ? acho que agora está mais claro.

O ~ inverte os bits da variável "valor2".

Você tem experiência como docente ?

Nenhuma.

joubet · 6 de março de 2007

Peguei a rotina que você disponibilizou, e chamei-a num programinha. Rodou redondinho. Veja:


#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

int agnerStrLen(char* str);
int main()
{
    char a[30]= "casa";
    int comprim =0;
    
   comprim=agnerStrLen(a);
   printf ("O comprimento e: %d\n ", comprim);
    system ("pause");   
    return(0);
}
int agnerStrLen(char* str)
{
    int* tmp = (int*)((int) str & -4);
    int durty = -1 << (((int) str - (int) tmp) << 3);
    unsigned int res = 0;
    int ret = 0;
    if(!(res = (0x80808080 & durty & ~(*tmp) & (*tmp - 0x01010101))))
        do{tmp++;}while(!(res = (0x80808080 & ~(*tmp) & (*tmp - 0x01010101))));
    ret = (int) tmp - (int) str;
    if(!(res & 0x8080))
    {
        res >>= 16;
        ret += 2;
    }
    if(!(res & 0x80))
        ret += 1;

    return ret;
}

O resultado ficou:

O comprimento é 4
Pressione qualquer tecla para continuar...

Dá observação da rotina, surgiram algumas dúvidas:

1- na linha:

int* tmp = (int*)((int) str & -4);

Entendi, que se está declarando uma variável que parece fazer um duplo cast - (int*)((int) – achei estranho, nunca vi isso, só vi coisa parecida quando se passa função como argumento.

1.1 - Entendi, que “str” é parâmetro da função mas não entendi o ‘& ‘ de bit –4

2- Na linha:

int durty = -1 << (((int) str - (int) tmp) << 3);

Não entendi a lógica desse deslocamento de bit, só sei, que se eu deslocar 1 a esquerda é como multiplicar por dois (ou quase)

3 – na linha:

if(!(res = (0x80808080 & durty & ~(*tmp) & (*tmp - 0x01010101))))

O que esse numero hexadecimal representa , e faz com estes vários “&”s de bit e o complemento a um ?

4) Por fim, você teria ou poderia me dizer onde baixar uma boa apostila que tratasse de operações com números binários e hexadecimais ?

Obrigado.

EduardoS · 7 de março de 2007

1- na linha:
int* tmp = (int*)((int) str & -4);
Entendi, que se está declarando uma variável que parece fazer um duplo cast - (int*)((int) – achei estranho, nunca vi isso, só vi coisa parecida quando se passa função como argumento.

Para poder fazer a operação "&" eu preciso converter para inteiro, e depois preciso converter para "int*" para ter o ponteiro onde vou trabalhar.

1.1 - Entendi, que “str” é parâmetro da função mas não entendi o ‘& ‘ de bit –4

O "& -4" alinha o ponteiro, isso traz duas vantagens:

1) Evita GPFs;

2) Melhora o desempenho já que os processadores atuais são mais rapidos para ler dados alinhados.

O ponteiro esta alinhado quando os bits menos significativos são zero e os demais apontem para um nova variavel a cada vez que incrementados...

No caso o "-4" alinha o ponteiro para variaveis de 4 bytes (um int 32bits, a escolha por 32 bits é porque a rotina foi feito para rodar em processadores assim), "& -8" seriam 8 bytes, etc

A representação negativa das pontencias de 2 em binário fica:

-2 = 11...1110

-4 = 11...1100

-8 = 11...1000

Ao fazer o and ele vai limpar os bits menos signifcativos e retornar o endereço alinhado.

2- Na linha:
int durty = -1 << (((int) str - (int) tmp) << 3);
Não entendi a lógica desse deslocamento de bit, só sei, que se eu deslocar 1 a esquerda é como multiplicar por dois (ou quase)

Deslocar 1 bit a esquerda equivale a multiplicar por 2, deslocar 2 bits equivale a multiplicar por 4, deslocar 3 bits equivale a multiplicar por 8, etc.

Quando alinhei o ponteiro no caso acima terei o seguinte problema:


byte 0    1    2    3
     |    +- inicio da string
     +----------- ponteiro alinhado

Ao carregar o valor apontado pelo ponteiro ele vai carregar o byte 0 e 1, mas que não interessam por não fazerem parte da string, a variavel durty vai criar uma mascara para que eu possa ignorar esses bytes,

Ao subtrair o ponteiro alinhado do ponteiro original eu terei quantos bytes preciso ignorar, multipliquei por 8 (o deslocamento a esquerda de 3 posições) para ter o número de bits que preciso ignorar e fiz um deslocamento desse número de bits no valor -1, preenchendo com 0 todos os bytes que preciso ignorar.

3 – na linha:
if(!(res = (0x80808080 & durty & ~(*tmp) & (*tmp - 0x01010101))))
O que esse numero hexadecimal representa , e faz com estes vários “&”s de bit e o complemento a um ?

O "& duty" serve para aplicar a mascara, o resto é o segredo do algoritimo:

O final da string é marcado por um byte com valor 0, posso ler byte a byte, mas leitura de memória é uma operação muito lenta, uma alternativa é ler 4 bytes por vez (vou chamar de A), como foi feito, mas ai preciso conseguir identificar se um dos bytes vale 0.

Para isso faço um and entre o complemento a um de A e A - 0x01010101, a lógica da segundo operação é subtrair 1 de cada byte, assim apenas os bytes que forem 0 ou 128 mudaram o bit de sinal, 0s 0 terão o bit de sinal 1, do 1 ao 128 terão o bit de sinal 0, do 129 em diante 1, o complemento a um vai inverter o sinal de todos os bytes, do 0 ao 127 terão o bit de sinal 1, do 128 em diante 0, ao fazer um and apenas os bytes que tiverem o bit de sinal 1 nas duas operações terão o bit de sinal 1 no resultado, e o único caso que isso acontece é com os bytes de valor 0, o 0x80808080 no começo é uma mascara para ele ignorar todos os bits que não forem o bit de sinal de cada byte, se no fim algum bit for diferente de 0 é porque acabou a string.