Quão bom um programador completo precisa ser com operações bit a bit? [fechadas]

Estive navegando em algum código do OpenJDK recentemente e encontrei algumas partes intrigantes de código que têm a ver com operações bit a bit . Eu até fiz uma pergunta sobre isso no StackOverflow.

Outro exemplo que ilustra o ponto:

 1141       public static int bitCount(int i) {
 1142           // HD, Figure 5-2
 1143           i = i - ((i >>> 1) & 0x55555555);
 1144           i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
 1145           i = (i + (i >>> 4)) & 0x0f0f0f0f;
 1146           i = i + (i >>> 8);
 1147           i = i + (i >>> 16);
 1148           return i & 0x3f;
 1149       }

Este código pode ser encontrado na classe Integer .

Não posso deixar de me sentir estúpido quando olho para isso. Eu perdi uma aula ou duas na faculdade ou isso não é algo que eu deveria ter ? Posso fazer operações simples em termos de bits (como ANDing, ORing, XORing, shifting), mas vamos lá, como alguém cria um código como esse acima?

Quão bom um programador completo precisa ser com operações bit a bit?

Em uma nota lateral ... O que me preocupa é que a pessoa que respondeu à minha pergunta no StackOverflow respondeu em questão de minutos. Se ele podia fazer isso, por que eu apenas olhava como veado nos faróis?

Eu diria que, como um desenvolvedor completo, você precisa entender os operadores e as operações bit a bit.

Portanto, no mínimo, você poderá descobrir o código acima depois de pensar um pouco.

As operações bit a bit tendem a ser de nível bastante baixo; portanto, se você trabalha em sites e software LOB, é improvável que os use muito.

Como outras coisas, se você não as usa muito, não estaria familiarizado com elas.

Portanto, você não deve se preocupar com alguém que possa descobrir isso rapidamente, pois eles (provavelmente) trabalham muito com esse tipo de código. Possivelmente escrevendo código do SO, código do driver ou outra manipulação de bits complicada.

Se você entender como resolver problemas como "determinar se os bits 3 e 8 estão definidos", "limpar o bit 5" ou "encontrar o valor inteiro representado pelos bits 7-12", você terá uma compreensão suficiente dos operadores bit a bit para verificar a opção Can Caixa de Twiddle Bits na lista de verificação "bem arredondada".

O que está no seu exemplo vem do Hacker's Delight , uma compilação de algoritmos de alto desempenho para manipular pequenos bits de dados como números inteiros. Quem escreveu esse código originalmente não o cuspiu em cinco minutos; a história por trás disso é mais provável que havia a necessidade de uma maneira rápida e sem ramificações de contar bits, e o autor teve algum tempo para olhar as seqüências de bits e criar uma maneira de resolver o problema. Ninguém vai entender como funciona de relance, a menos que já tenha visto isso antes. Com uma sólida compreensão dos conceitos básicos de bits e algum tempo gasto experimentando o código, você provavelmente pode descobrir como ele faz o que faz.

Mesmo que você não entenda esses algoritmos, apenas saber que eles existem aumenta a sua "redondeza", porque quando chega a hora de lidar com, por exemplo, a contagem de bits de alto desempenho, você sabe o que estudar. No mundo pré-Google, era muito mais difícil descobrir essas coisas; agora estão pressionadas as teclas.

O usuário que respondeu à sua pergunta de SO pode ter visto o problema antes ou estudado o hash. Escreva para ele e pergunte.

Do seu exemplo, há algumas coisas que você absolutamente deve saber sem realmente pensar.

1143 i = i - ((i >>> 1) & 0x55555555);

Você deve reconhecer o padrão de bits 0x555 ... como um padrão de bits alternativo 0101 0101 0101 e que os operadores o compensam em 1 bit (à direita), e que & é uma operação de mascaramento (e o que significa mascarar).

1144 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

Novamente um padrão, este é 0011 0011 0011. Também está mudando dois dessa vez e mascarando novamente. a mudança e a máscara estão seguindo um padrão que você deve reconhecer ...

1145 i = (i + (i >>> 4)) & 0x0f0f0f0f;

o padrão solidifica. Desta vez, é 00001111 00001111 e, é claro, estamos mudando para 4 desta vez. cada vez que mudamos de tamanho da máscara.

1148 retornar i & 0x3f;

outro padrão de bits, 3f é um bloco de zeros seguido por um bloco maior de zeros.

Todas essas coisas devem ser óbvias à primeira vista se você estiver "bem arredondado". Mesmo que você nunca pense que vai usá-lo, provavelmente perderá algumas oportunidades para simplificar amplamente seu código, se não souber disso.

Mesmo em um idioma de nível superior, os padrões de bits são usados ​​para armazenar MUITAS quantidades maiores de dados em campos menores. É por isso que você sempre vê limites de 127/8, 63/4 e 255/6 nos jogos, é porque você precisa armazenar tantas dessas coisas que, sem empacotar os campos, você será forçado a usar até dez vezes o valor quantidade de memória. (Bem, o melhor seria se você precisasse armazenar um grande número de booleanos em uma matriz, economizando 32 a 64 vezes a quantidade de memória que usaria se não pensasse nisso - a maioria das linguagens implementa booleanos como uma palavra que geralmente terá 32 bits. Aqueles que não se sentem confortáveis ​​nesse nível resistirão a oportunidades de armazenar dados como esse simplesmente porque têm medo do desconhecido.

Eles também se esquivam de coisas como analisar manualmente pacotes entregues pela rede em um formato compactado - algo que é trivial se você não tiver medo. Isso pode levar um jogo que requer um pacote de 1k a 200 bytes, o pacote menor desliza pela rede com mais eficiência, reduz a latência e permite maiores velocidades de interação (o que pode possibilitar novos modos de jogo para um jogo).

Por acaso reconheci o código porque já o vi anteriormente em software para manipulação de quadros de vídeo. Se você trabalhasse regularmente com coisas como CODECs de áudio e vídeo, protocolos de rede ou registradores de chips, veria muitas operações bit a bit e isso se tornaria uma segunda natureza para você.

Você não deve se sentir mal se o seu trabalho não coincidir com esses domínios com muita frequência. Conheço bem as operações bit a bit, mas desacelero nas raras ocasiões em que preciso escrever uma GUI, por causa de todas as peculiaridades com layouts, ponderação e expansão, e de modo que tenho certeza que são uma segunda natureza para os outros. Seus pontos fortes estão onde quer que você tenha mais experiência.

as principais coisas que você deve estar ciente é como os números inteiros são representados (em geral, um vetor de bits de comprimento fixo em que o comprimento depende da plataforma) e quais operações estão disponíveis neles

as principais operações aritméticas + - * / %podem ser entendidas sem a necessidade de entendê-las, embora possam ser úteis para micro-otimizações (embora na maioria das vezes o compilador possa cuidar disso para você)

o conjunto de manipulação de bits | & ~ ^ << >> >>>requer pelo menos um entendimento de passagem para poder usá-los

no entanto, na maioria das vezes, você os usará apenas para passar sinalizadores de bit para um método, ORao mesmo tempo em que passa e passa um int e, em seguida, ANDsai as configurações mais legíveis do que passar vários (até 32) booleanos em uma longa lista de parâmetros e permite os possíveis sinalizadores a serem alterados sem alterar a interface

sem mencionar que os booleanos geralmente são mantidos separadamente em bytes ou ints, em vez de agrupá-los como as bandeiras

quanto ao trecho de código, ele faz uma contagem paralela dos bits, permitindo que o algoritmo seja executado O(log(n))onde n é o número de bits em vez do loop ingênuo que éO(n)

o primeiro passo é o mais difícil de entender, mas se você começar a partir da configuração, ele precisará substituir as seqüências de bits 0b00para 0b00, 0b01para 0b01, 0b10para 0b01e 0b11para 0b10que fique mais fácil seguir

Portanto, para o primeiro passo, i - ((i >>> 1) & 0x55555555)se considerarmos ique é igual a 0b00_01_10_11, a saída disso deve ser0b00_01_01_10

(note que 0x5é igual a 0b0101)

Se tomarmos i = 0b00_01_10_11isso significa que 0b00_01_01_10 - (0b00_00_11_01 & 0b01_01_01_01)é o 0b00_01_10_11 - 0b00_00_01_01que por sua vez se torna0b00_01_01_10

eles poderiam ter feito (i & 0x55555555) + ((i >>> 1) & 0x55555555)pelo mesmo resultado, mas esta é uma operação adicional

os seguintes passos estão na mesma linha

Todos devem entender operações básicas em bits. É a composição das operações básicas para executar tarefas de uma maneira otimizada e robusta que requer muita prática.

Aqueles que trabalham com manipulação de bits todos os dias (como pessoas incorporadas) estão, é claro, desenvolvendo uma forte intuição e uma bela bolsa de truques.

Quanta habilidade deve ter um programador que não faz coisas de baixo nível com manipulação bit a bit? O suficiente para poder sentar-se com uma estrofe como você colou e trabalhar com ela lentamente, como se fosse um quebra-cabeça ou quebra-cabeça.

Da mesma forma, eu diria que um programador incorporado deve entender tanto sobre http quanto um desenvolvedor da Web entende sobre manipulação em bits. Em outras palavras, não há problema em não ser manipulado se você não estiver usando o tempo todo.

O prazer do hacker é um trabalho derivado. O ancestral de todos é o HakMem de 1972. http://w3.pppl.gov/~Hammett/work/2009/AIM-239-ocr.pdf

O importante é saber que o algoritmo óbvio para qualquer tarefa não é necessariamente o melhor. Existem muitos casos em que é importante conhecer a existência de uma solução elegante para um problema partucular.

Quão difícil é a interpretação dos operadores bit a bit?

Eu programo sistemas embarcados. Eu pratiquei muito essas coisas. Sua pergunta vinculada sobre mapas de hash com o código

static int hash(int h) {
   // This function ensures that hashCodes that differ only by
   // constant multiples at each bit position have a bounded
   // number of collisions (approximately 8 at default load factor).
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

fez todo o sentido para mim em quanto tempo levaria para ditar o código em voz alta. Os eventos descritos em bitCountsão imediatamente claros, mas leva um minuto para descobrir por que ele realmente conta os bits. Os comentários seriam ótimos, porém, e tornariam a compreensão do que o código faz apenas um pouco mais difícil do que o problema de hash.

É importante fazer a distinção entre ler e entender o código. Eu posso interpretar o bitCountcódigo e ler o que ele faz, mas provar por que funciona ou mesmo que levaria um minuto. Há uma diferença entre ser capaz de ler o código sem problemas e saber por que o código é do jeito que é. Alguns algoritmos são simplesmente difíceis. O que o hashcódigo fazia sentido, mas o comentário explica por que o que estava sendo feito. Não desanime se uma função que usa operadores bit a bit é difícil de entender, eles costumam ser usados ​​para fazer coisas matemáticas complicadas que seriam difíceis, independentemente do formato.

Uma analogia

Estou acostumado a essas coisas. Um assunto que eu não estou acostumado é regex. Ocasionalmente, trato deles em scripts de construção, mas nunca no trabalho diário de desenvolvimento.

Eu sei como usar os seguintes elementos de uma regex:

• [] classes de personagem
• Os *, .e +wildcards
• O início da sequência ^e o final da sequência$
• As classes de caracteres \ d, \ w e \ s
• O sinalizador / g

Isso é suficiente para criar consultas simples, e muitas das consultas que vejo não se afastam disso.

Qualquer coisa que não esteja nesta lista, pego uma folha de dicas. Qualquer coisa, exceto, {}e ()- A cola não será suficiente. Eu sei o suficiente sobre esses caras para saber que vou precisar de um quadro branco, um manual de referência e talvez um colega de trabalho. Você pode agrupar alguns algoritmos malucos em algumas linhas curtas de regex.

Para criar um regex que exija ou sugira qualquer coisa que não esteja na minha lista de elementos conhecidos, vou listar todas as classes de entradas que espero reconhecer e colocá-las em um conjunto de testes. Vou criar o regex lenta e incrementalmente, com muitas etapas intermitentes, e confirmar essas etapas para controlar a fonte e / ou deixá-las em um comentário para que eu possa entender o que deveria acontecer mais tarde, quando ocorrer uma quebra. Se estiver no código de produção, vou garantir que seja revisado por alguém com mais experiência.

É aqui que você está com operadores bit a bit?

Então você quer ser bem arredondado?

Na minha opinião, se você é capaz de interpretar o que esse código faz, puxando um pedaço de papel ou indo para o quadro branco e executando as operações manualmente, você se qualifica como completo. Para se qualificar como um bom programador completo na área de operações bit a bit, você deve ser capaz de fazer quatro coisas:

1. Ser capaz de ler e gravar operações comuns de maneira fluida
   Para um programador de aplicativos, as operações comuns com operadores bit a bit incluem os operadores básicos de |e &para definir e limpar sinalizadores. Isso deve ser fácil. Você deve ler e escrever coisas como

   open('file', O_WRONLY | O_APPEND | O_CREAT );
   // Use an OR operator ^ here and ^ here to set multiple flags
   

   sem diminuir a velocidade (supondo que você saiba o que as bandeiras significam ).

2. Consiga ler operações mais complexas com algum trabalho
   Contando bits muito rapidamente no tempo O (log (n)) sem ramificações, garantindo que o número de colisões em hashCodes possa diferir por uma quantidade limitada e analisando endereços de email , números de telefone ou HTML com um regex são problemas difíceis. É razoável que qualquer pessoa que não seja especialista nessas áreas procure o quadro branco, não é razoável ser incapaz de começar a trabalhar para entender.

3. Seja capaz de escrever algoritmos complexos com muito trabalho
   Se você não é um especialista, não deve esperar fazer coisas complexas e difíceis. No entanto, um bom programador deve conseguir fazer isso trabalhando continuamente. Faça isso o suficiente, e em breve você será um especialista :)

Se você estudou em uma universidade decente, deveria ter aulas de Matemática Discreta. Você teria aprendido aritmética binária, octal e hexadecimal e portas lógicas.

Na mesma nota, é normal sentir-se confuso com isso, se isso lhe serve de consolo, porque eu escrevo aplicativos da Web, raramente preciso olhar ou escrever código assim, mas como entendo a aritmética binária e o comportamento dos operadores bit a bit Eu posso finalmente descobrir o que está acontecendo aqui, com tempo suficiente.

Como programador de telefones celulares, tive que lidar com esse tipo de coisa. É razoavelmente comum quando o dispositivo não tem muita memória ou onde a velocidade de transmissão é importante. Nos dois casos, você procura compactar o máximo possível de informações em alguns bytes.

Não me lembro de usar operadores bit a bit em 5 anos ou mais de PHP (talvez seja apenas eu), não em 10 anos ou mais de programação do Windows, embora algumas coisas do Windows de nível inferior compor bits.

Você diz "Não posso deixar de me sentir estúpido quando olho para isso". NÃO - sinta raiva.

Você acabou de conhecer a saída de um programador de caubói.

Ele não sabe nada sobre como escrever código sustentável? Eu sinceramente espero que ele seja o único que volte a isso daqui a um ano e tente lembrar o que isso significa.

Não sei se você cortou comentários ou se não houve, mas esse código não passaria na revisão de código onde eu era gerente de controle de qualidade s / w (e já estive algumas vezes).

Aqui está uma boa regra geral - os únicos "números inteiros" permitidos no código são 0 1 e 1. Todos os outros números devem ser #defines, custos, enumerações etc., dependendo do seu idioma.

Se esses 3 e 0x33333333 disserem algo como NUM_WIDGET_SHIFT_BITS e WIDGET_READ_MASK, o código seria mais fácil de ler.

Que vergonha para quem publicou isso em um projeto de código-fonte aberto, mas mesmo para o código pessoal, comente bem e use define / enums significativos e tenha seus próprios padrões de codificação.

Esse código em particular é retirado do livro Hacker's Delight , figura 5.2. Está online em C (a função pop) aqui . Observe que o autor agora recomenda o uso de versões atualizadas: http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.c.txt

Se você quiser aprender esse tipo de micro-otimização, sugiro esse livro; é divertido, mas a menos que você esteja fazendo programação de bits de nível muito baixo, provavelmente não entenderá; e na maioria das vezes o seu compilador poderá fazer muitos desses tipos de otimizações para você.

Também ajuda a reescrever todos os números hexadecimais em binário para entender esses tipos de algoritmos e trabalhar com eles em um ou dois casos de teste.

Explicação por exemplo. Dados são sequências de bits. Vamos contar os bits no byte 01001101, com as seguintes operações disponíveis: 1. Podemos verificar o valor do último bit. 2. Podemos mudar a sequência.

1. 01001101 -> último byte é 1, total = 1. turnos
2. 10100110 -> último byte é 0, total = 1. turnos
3. 01010011 -> último byte é 1, total = 2. turnos
4. 10101001 -> último byte é 1, total = 3. turnos
5. 11010100 -> último byte é 0, total = 3. turnos
6. 01101010 -> último byte é 0, total = 3. turnos
7. 00110101 -> último byte é 1, total = 4. turnos
8. 10011010 -> último byte é 0, total = 4. turnos

Nossa resposta: 4.

Isso não foi difícil, foi? O grande problema das operações bit a bit é que existem coisas limitadas que podemos fazer. Não podemos acessar um pouco diretamente. Mas podemos, por exemplo, saber o valor do último bit comparando-o com a MASK 00000001 e podemos fazer com que cada bit seja o último com operações de deslocamento. Obviamente, o algoritmo resultante parecerá assustador para quem não está acostumado. Nada a ver com inteligência.

Eu não diria que você precisa, a menos que o trabalho que você está fazendo esteja relacionado a:

• Processamento de áudio
• Processamento de vídeo
• Gráficos
• Rede (particularmente onde o tamanho do pacote é importante)
• Enormes quantidades de dados

O armazenamento de permissões em sinalizadores de estilo unix também é outro uso, se você tiver um modelo de permissões particularmente complexo para o seu sistema ou realmente desejar compactar tudo em um único byte, à custa da legibilidade.

Além dessas áreas, eu consideraria uma grande vantagem se um desenvolvedor / desenvolvedor sênior pudesse demonstrar uma mudança de bits e usar | & e ^, pois mostra um interesse na profissão que você poderia dizer que leva a um código mais estável e confiável.

Na medida em que não 'obtém' o método à primeira vista, como mencionado, você precisa de uma explicação sobre o que está fazendo e de alguns antecedentes. Eu não diria que está relacionado à inteligência, mas como você está familiarizado com o trabalho hexadecimal no dia-a-dia e com o reconhecimento de problemas que certos padrões podem resolver.