Para que servem os operadores de bits? [fechadas]

19

As linguagens de programação geralmente vêm com vários operadores de bits (por exemplo, deslocamento bit a esquerda e direita, bit a bit AND, OR, XOR ...). Eles não se acostumam muito, ou pelo menos essa tem sido minha experiência. Às vezes, são usados ​​em desafios de programação ou perguntas de entrevistas, ou a solução pode exigir deles, por exemplo:

  • Sem usar nenhum operador de igualdade, crie uma função que retorne truequando dois valores forem iguais
  • Sem usar uma terceira variável, troque o valor de duas variáveis

Estes, então, novamente, provavelmente têm poucos usos no mundo real . Eu acho que eles deveriam ser mais rápidos porque manipulam diretamente a memória em um nível baixo.

Por que esses são encontrados na maioria das linguagens de programação? Algum caso de uso no mundo real?

Anto
fonte
@ Anto - Um exemplo fácil seria enviar 256 KB de dados a uma taxa de 256 palavras por vez (4096 bytes) para um cliente.
Ramhound
1
"Sem usar nenhum operador de igualdade, crie uma função que retorne true quando dois valores forem iguais" - em C return !(x-y);:? Eu não sei
Andrew Arnold
@ Andrew: Essa é uma solução, mas você também pode fazê-lo com operadores bit a bit.
Anto
19
"Eles não se acostumam muito" - Tem certeza disso? Eu os uso o tempo todo. Nem todos trabalhamos no domínio do seu problema.
Ed S.
2
Não é suficiente para uma resposta completa, mas tente ler os 4 bits de um byte sem bit mexer e então considerar que alguns formatos de dados são muito bem embalado.
Restabeleça Monica

Respostas:

53

Não, eles têm muitos aplicativos do mundo real e são operações fundamentais em computadores.

Eles são usados ​​para

  • Manipulando blocos de bytes que não cabem nos tipos de dados das linguagens de programação
  • Alternando a codificação para frente e para trás do grande para o pequeno endian.
  • Empacotando 4 pedaços de dados de 6 bits em 3 bytes para alguma conexão serial ou usb
  • Muitos formatos de imagem têm diferentes quantidades de bits atribuídos a cada canal de cores.
  • Qualquer coisa envolvendo pinos de E / S em aplicativos incorporados
  • Compactação de dados, que geralmente não possui dados, se encaixa nos limites de 8 bits. \
  • Algoritmos de hash, CRC ou outras verificações de integridade de dados.
  • Criptografia
  • Geração de números aleatórios
  • O Raid 5 usa o XOR bit a bit entre volumes para calcular a paridade.
  • Toneladas mais

De fato, logicamente, todas as operações em um computador acabam se resumindo a combinações dessas operações de baixo nível de bits, ocorrendo dentro dos portões elétricos do processador.

whatsisname
fonte
1
+1 para a sua lista bastante abrangente, que até parecem estar aumentando
Anto
28
+1. @ Anto: Esta lista não é nem de longe abrangente. Uma lista abrangente de casos de uso para operadores bit a bit na programação de sistemas seria uma lista abrangente para consultas SQL em aplicativos de negócios. Curiosidade: Eu uso operações bit a bit o tempo todo, mas não tenho escrito uma instrução SQL em anos ;-)
Nikie
4
@nikie: E eu escrevo SQL o tempo todo, mas não utilizo operadores bit a bit há anos! :)
FrustratedWithFormsDesigner
3
Eu trabalho em sistemas embarcados - operadores bit a bit são coisas de pão com manteiga. Usado todos os dias sem qualquer pensamento.
quickly_now
9
Se eu ocasionalmente usar deslocamento de bits no SQL, recebo um prêmio?
Ant
13

Porque são operações fundamentais.

Pela mesma linha de pensamento, você poderia argumentar que a adição tem poucos usos no mundo real, pois pode ser substituída completamente por subtração (e negação) e multiplicação. Mas mantemos a adição porque é uma operação fundamental.

E não pense por um momento que só porque você não viu muita necessidade de operações bit a bit não significa que elas não sejam usadas com muita frequência. Na verdade, eu usei operações bit a bit em quase todos os idiomas que usei para coisas como mascaramento de bits.

Em primeiro lugar, usei operações bit a bit para processamento de imagem, campos de bits e sinalizadores, processamento de texto (por exemplo, todos os caracteres de uma classe específica geralmente compartilham um padrão de bits comum), codificando e decodificando dados serializados, decodificando VM ou CPU códigos de operação e assim por diante. Sem operações bit a bit, a maioria dessas tarefas exigiria operações muitas vezes mais complexas para executar a tarefa com menos confiabilidade ou com menor legibilidade.

Por exemplo:

// Given a 30-bit RGB color value as a 32-bit int
// A lot of image sensors spit out 10- or 12-bit data
// and some LVDS panels have a 10- or 12-bit format
b = (color & 0x000003ff);
g = (color & 0x000ffc00) >> 10;
r = (color & 0x3ff00000) >> 20;

// Going the other way:
color = ((r << 20) & 0x3ff00000) | ((g << 10) & 0x000ffc00) | (b & 0x000003ff);

A decodificação de instruções da CPU para CPUs do tipo RISC (como ao emular outra plataforma) requer a extração de partes de um valor grande, como acima. Às vezes, fazer essas operações com multiplicação, divisão, módulo, etc., pode ser até dez vezes mais lento que o equivalente em operações bit a bit.

desvanecer-se
fonte
12

Um exemplo típico é extrair as cores individuais de um valor RGB de 24 bits e vice-versa.


EDIT: From http://www.docjar.com/html/api/java/awt/Color.java.html

    value =  ((int)(frgbvalue[2]*255 + 0.5))    |
                (((int)(frgbvalue[1]*255 + 0.5)) << 8 )  |
                (((int)(frgbvalue[0]*255 + 0.5)) << 16 ) |
                (((int)(falpha*255 + 0.5)) << 24 );

fonte
Mostrar este exemplo na prática? Um trecho de código?
Anto 05/04
Um exemplo melhor pode ser o processamento de valores RGB de 16 bits (4,5bpc) ou 30 bits (10bpc).
greyfade
@ Grey, fique à vontade para adicionar exemplos.
6

Aqui está um exemplo do mundo real que você encontrará no Quake 3, Quake 4. Doom III. Todos aqueles jogos que usaram o mecanismo Q3 .

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking [sic]
        i  = 0x5f3759df - ( i >> 1 );               // what the fuck? [sic]
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

        return y;
}

(Para entender esse código, você precisa entender como os números de ponto flutuante são armazenados, definitivamente não posso elaborar isso)

Em termos de uso, a menos que você esteja em campos que exigem mudança de bits, como redes ou gráficos, você pode achar o objetivo deles levemente acadêmico. Mas ainda é interessante (pelo menos para mim).

Chris S
fonte
+1 Para esses comentários, mesmo que não sejam seus. Me fez rir.
Bassinator
4

Mudar é mais rápido do que multiplicar ou dividir por uma potência de dois. Por exemplo, a << = 2 multiplica a por 4. Por outro lado, a >> = 2 divide a por quatro. Também é possível enviar dados por bit para um dispositivo usando os operadores bit a bit. Por exemplo, podemos enviar N fluxos de dados seriais a partir de uma porta N pinos usando shift, xor e "e" operações dentro de N loops. Tudo o que pode ser realizado em lógica digital também pode ser realizado em software e vice-versa.

bit-twiddler
fonte
1
Apenas tenha cuidado ao dividir com arredondamento para cima ou para baixo, etc. A mudança não explica isso, então eu achei realmente uma prática melhor usar uma divisão no código quando eu quero dizer uma divisão e deixar o compilador otimizá-lo em um turno e adicionar para mim.
Daemin #
@ Daemin: Eu estou trabalhando com números inteiros quando eu uso essa técnica. O comportamento padrão para a divisão inteira em C e C ++ é truncamento em direção a zero; portanto, mudar um número inteiro para a direita por uma potência de dois produz o mesmo resultado que dividir um número inteiro por uma potência de dois.
bit-twiddler
1
@ bit-twiddler O deslocamento à direita não funciona da mesma maneira que a divisão para números negativos.
Daemin 7/11
@ Daemin: Você parece estar decidido a provar que estou errado. Primeiro, você lança o problema de arredondamento. Quando repudia essa afirmação, afirmando que a divisão em C e C ++ trunca em direção a zero, você lança o problema de número inteiro assinado. Onde eu disse que estava aplicando o operador shift aos números inteiros negativos do complemento de dois assinados? Com isso dito, ainda é possível usar o operador de turno para dividir por uma potência de dois. No entanto, como C e C ++ realizam um deslocamento à direita aritmético em vez de um deslocamento à direita antigo e simples, é preciso primeiro verificar se o valor é negativo. Se o valor for negativo,
bit-twiddler
1
Exatamente, tenha cuidado ao usar o deslocamento como um substituto para multiplicação e divisão, pois existem diferenças sutis. Nem mais nem menos.
Daemin
3

Há muito tempo, os operadores de bits eram úteis. Hoje eles são menos. Oh, eles não são totalmente inúteis, mas faz muito tempo desde que eu vi um usado que deveria ter sido usado.

Em 1977 eu era um programador de linguagem assembly. Eu estava convencido que assembler era a única linguagem verdadeira. Eu tinha certeza de que uma linguagem como Pascal era para estudantes acadêmicos que nunca precisavam fazer nada real .

Então li "The C Programming Language", de Kernighan e Ritchie. Isso mudou minha mente completamente. O motivo? Tinha pouco operadores! Ele era uma linguagem de montagem! Só tinha uma sintaxe diferente.

Naqueles dias, eu não conseguia pensar em escrever código sem ands, ors, turnos e rotações. Hoje em dia quase nunca os uso.

Portanto, a resposta curta para sua pergunta é: "Nada". Mas isso não é justo. Portanto, a resposta mais longa é: "Principalmente nada".

Tio Bob.
fonte
xkcd.com/378 vem à mente.
Maxpm
Operadores de bit são úteis até hoje. O fato de que no seu domínio eles não são usados ​​não o torna não utilizado ou mesmo não é usado com muita frequência. Aqui está um exemplo simples: tente implementar o AES sem operadores de bits. Esse é um exemplo simples de algo que é feito na maioria dos computadores diariamente centenas ou milhares de vezes por dia.
APENAS MINHA OPINIÃO correta
Codificar / decodificar dados sem usar operadores bit a bit é doloroso, na melhor das hipóteses. Por exemplo, adicionar anexos MIME a uma mensagem exige que possamos lidar com a codificação de três a quatro dos dados (também conhecida como codificação radix64).
precisa saber é o seguinte
2

Criptografia

Sugiro dar uma olhada em um pequeno trecho do algoritmo de criptografia DES :

temp = ((left >>> 1) ^ right) & 0x55555555; right ^= temp; left ^= (temp << 1);
temp = ((right >>> 8) ^ left) & 0x00ff00ff; left ^= temp; right ^= (temp << 8);
temp = ((right >>> 2) ^ left) & 0x33333333; left ^= temp; right ^= (temp << 2);
temp = ((left >>> 16) ^ right) & 0x0000ffff; right ^= temp; left ^= (temp << 16);
temp = ((left >>> 4) ^ right) & 0x0f0f0f0f; right ^= temp; left ^= (temp << 4);
Scott Whitlock
fonte
Embora não tenho certeza DES é recomendado nestes dias: P
Armand
@ Alison: Não, mas acho que os algoritmos de criptografia que o substituíram envolvem ainda mais operações de manipulação de bits. :-)
Carson63000
@ Alison - é claro, mas o TripleDES é apenas DES feito 3 vezes com 3 vezes os bits de chave.
Scott Whitlock
2

Muitas respostas boas, então não repetirei esses usos.

Eu os uso bastante em código gerenciado (C # / .Net), e não tem nada a ver com economia de espaço, alto desempenho ou algoritmos inteligentes de troca de bits. Às vezes, alguma lógica é adequada para armazenar dados dessa maneira. Costumo usá-los quando tenho uma enumeração, mas as instâncias podem receber simultaneamente vários valores dessa enumeração. Não consigo postar um exemplo de código do trabalho, mas um rápido google para "Flags enum" ("Flags" é a maneira C # de definir uma enum para ser usada de maneira bit a bit) fornece este exemplo: http: // www.dotnetperls.com/enum-flags .

Steve
fonte
2

Também há computação paralela em bits. Se seus dados são apenas 1 e 0, você pode agrupar 64 deles em uma palavra longa e não assinada e obter operações paralelas de 64 vias. A informação genética é de dois bits (representando a codificação AGCT do DNA) e, se você puder fazer os vários cálculos de maneira paralela aos bits, poderá fazer muito mais do que se não o fizer. Sem mencionar a densidade de dados na memória - se a memória, a capacidade do disco ou a largura de banda de comunicação são limitadas, implica que a compactação / descompactação deve ser considerada. Mesmo números inteiros de baixa precisão, que aparecem em áreas como processamento de imagem, podem tirar proveito da computação paralela de bits complicada. É uma arte inteira em si mesma.

Omega Centauri
fonte
1

Por que eles são encontrados?

Bem, isso é provavelmente porque eles correspondem às instruções de montagem e, às vezes, são úteis apenas para coisas em idiomas de nível superior. O mesmo se aplica ao temido GOTOque corresponde à JMPinstrução de montagem.

Quais são os usos deles?

Realmente, existem muitos usos para citar, então darei um uso recente, embora altamente localizado. Eu trabalho muito com a montagem 6502 e estava trabalhando em um pequeno aplicativo que converte endereços de memória, valores, compara valores etc. em códigos que podem ser usados ​​para o dispositivo GameGenie (basicamente um aplicativo de trapaça para o NES). Os códigos são criados por alguma manipulação de bits.


fonte
1

Atualmente, muitos programadores estão acostumados a computadores com memória quase infinita.

Mas alguns aplicativos ainda programam minúsculos microcontroladores onde cada bit conta (quando você tem apenas 1k ou menos de RAM, por exemplo), e os operadores bit a bit permitem que um programador use esses bits um por vez, em vez de desperdiçar uma programação muito maior entidade de abstração que possa ser necessária para manter algum estado exigido pelo algoritmo. O IO nesses dispositivos também pode exigir a leitura ou o controle bit a bit.

O "mundo real" possui muito mais desses minúsculos microcontroladores do que servidores ou PCs.

Para tipos puramente teóricos de CS, as máquinas de Turing tratam de bits de estado.

hotpaw2
fonte
1

Apenas mais um dos muitos usos possíveis dos operadores bit a bit ...

Os operadores bit a bit também podem ajudar a tornar seu código mais legível. Considere a seguinte declaração de função ....

int  myFunc (bool, bool, bool, bool, bool, bool, bool, bool);

...

myFunc (false, true, false, false, false, true, true, false);

É muito fácil esquecer qual parâmetro booleano significa o que ao escrever ou mesmo ler o código. Também é fácil perder o controle da sua contagem. Essa rotina pode ser limpa.

/* More descriptive names than MY_FLAGx would be better */
#define MY_FLAG1    0x0001
#define MY_FLAG2    0x0002
#define MY_FLAG3    0x0004
#define MY_FLAG4    0x0008
#define MY_FLAG5    0x0010
#define MY_FLAG6    0x0020
#define MY_FLAG7    0x0040
#define MY_FLAG8    0x0080

int  myFunc (unsigned myFlags);

...

myFunc (MY_FLAG2 | MY_FLAG6 | MY_FLAG7);

Com nomes de sinalizadores mais descritivos, torna-se muito mais legível.

Sparky
fonte
1

Se você conhece alguma coisa sobre Unicode , provavelmente conhece o UTF-8. Ele usa vários testes, turnos e máscaras de bits para compactar o ponto de código de 20 bits em 1 a 4 bytes.

MSalters
fonte
0

Não os estou usando com frequência, mas às vezes eles são úteis. O manuseio de enum vem à mente.

Exemplo:

enum DrawBorder{None = 0, Left = 1, Top = 2, Right = 4, Bottom = 8}

DrawBorder drawBorder = DrawBorder.Left | DrawBorder.Right;//Draw right & left border
if(drawBorder & DrawBorder.Left == DrawBorder.Left)
  //Draw the left border
if(drawBorder & DrawBorder.Top == DrawBorder.Top)
  //Draw the top border
//...
Carra
fonte
0

Não tenho certeza se esse uso já foi observado:

Eu vejo muito o OR ao trabalhar com o código fonte illumos (openSolaris) para reduzir vários valores de retorno para 0 ou 1, por exemplo

int ret = 0;
ret |= some_function(arg, &arg2); // returns 0 or 1
ret |= some_other_function(arg, &arg2); // returns 0 or 1
return ret;
Awalias
fonte