Números divertidos: 0xAAAAAAAA e seu irmão 0x55555555

Ontem estava começando a ler um livro, chamado Hacker's Delight (hacker no sentido original, fuçador e escovador de bits), meio desconfiado porque ele me foi indicado por um colega que é engenheiro de compiladores (bichos raros e bizarros). Ficava pensando se eu realmente iria gostar de ler sobre centenas de operações curiosas e micro-algoritmos otimizados em um assembly RISC hipotético e aritmética modular (claro que sim).

Eis que no prefácio o livro já me cativou, falando sobre as correções do Guy Steele e sobre os fatores do número hexadecimal 0xAAAAAAAA, que são 2, 5, 17, 257 e 65537. Quem fuça em bits desde pequeno já deve ter ficado intrigado pelo 65537 e pelo 257, e talvez também pelos outros (mas o 2 meio que sobra, veremos o porquê). Observando um pouco os números, e brincando com os comandos factor e bc, eis que percebi que realmente os números 0xAA... e 0x55... (em 8, 16 e 32 bits) são números muito bonitos e divertidos. :)

Comecemos pelo 0xAAAAAAAA mencionado no livro. Sua representação em binário é 10101010101010101010101010101010, e em octal é 25252525252 (que inclusive é um palíndromo). Em decimal dá um 2863311530 chato. Mas agora olhemos os seus fatores 2, 5, 17, 257 e 65537:

    2 = 4 ^ 0 + 1

    5 = 4 ^ 1 + 1

   17 = 4 ^ 2 + 1

  257 = 4 ^ 4 + 1

65537 = 4 ^ 8 + 1

Se não fosse pelo 2 (chato), dava ainda pra fazer outra série mais bonita:

    5 = 2 ^ 2 ^ 1 + 1

   17 = 2 ^ 2 ^ 2 + 1

  257 = 2 ^ 2 ^ 3 + 1

65537 = 2 ^ 2 ^ 4 + 1

Em binário, o 2 fica chato, mas os demais ficam bonitos:

    2 = 10

    5 = 101

   17 = 10001

  257 = 100000001

65537 = 10000000000000001

O legal é que, como este número divertido 0xAAAAAAAA tem 2 (chato) como fator, fica óbvio que teremos outro número bonito e divertido retirando o 2 dos fatores (dividindo por 2, ou deslocando um bit pra direita): 0x55555555. Como tiramos o 2 da história, os fatores ficam 5, 17, 257 e 65537, que são todos números bonitos e dão séries contínuas de exponenciação como visto acima. :)

0x55555555 em binário é 01010101010101010101010101010101 e em octal fica um pouco menos bonito que o seu irmão: 12525252525. Em decimal fica um desinteressante 1431655765. E pra fechar, olhem que massa: as versões menores destes números de 32bits também continuam interessantes, e a série de fatores deles fica interessantíssima!

    fatores de 0x55 = 5 17

  fatores de 0x5555 = 5 17 257

fatores de 0x555555 = 5 17 257 65537

O mesmo acontece com 0xAA, 0xAAAA e 0xAAAAAA, somente adicionando o 2 inicial. :) Pena que indo pra 64bits aí já entram outros fatores menos divertidos.

Update: Acabaram as reuniões do dia. Mais diversão com o bc pra ver que a série continua bem legal:

$ bc
bc 1.06.95
...

2 ^ 2 ^ 5 + 1
4294967297
 

2 ^ 2 ^ 6 + 1
18446744073709551617

obase=16
 

5 * 17 * 257 * (2 ^ 2 ^ 5 + 1)
555500005555
 

2 * 5 * 17 * 257 * (2 ^ 2 ^ 5 + 1)
AAAA0000AAAA
 

5 * 17 * 257 * (2 ^ 2 ^ 5 + 1) * (2 ^ 2 ^ 6 + 1)
5555000055550000555500005555
 

2 * 5 * 17 * 257 * (2 ^ 2 ^ 5 + 1) * (2 ^ 2 ^ 6 + 1)
AAAA0000AAAA0000AAAA0000AAAA
... e assim por diante. :)