Como isso imprime "olá mundo"?

163

Eu descobri essa estranheza:

for (long l = 4946144450195624l; l > 0; l >>= 5)
    System.out.print((char) (((l & 31 | 64) % 95) + 32));

Resultado:

hello world

Como é que isso funciona?

Boêmio
fonte
14
Quero dizer, você pode descobrir isso sozinho.
Sotirios Delimanolis
30
Sim. Eu admito ... estou pescando chapéus :)
Bohemian
6
Eu acho que já vi essa pergunta feita aqui antes ..
Zavior
6
@ Oli Deve haver um chapéu para isso.
Sotirios Delimanolis
12
Perguntas como essa, que não melhoram o banco de dados, mas existem apenas como clickbait, são uma maneira infalível de cancelar o jogo Hat no futuro. Por favor, não estrague o jogo se prostituindo.
Blazemonger

Respostas:

256

O número 4946144450195624cabe 64 bits, sua representação binária é:

 10001100100100111110111111110111101100011000010101000

O programa decodifica um caractere para cada grupo de 5 bits, da direita para a esquerda

 00100|01100|10010|01111|10111|11111|01111|01100|01100|00101|01000
   d  |  l  |  r  |  o  |  w  |     |  o  |  l  |  l  |  e  |  h

Codificação de 5 bits

Para 5 bits, é possível representar 2⁵ = 32 caracteres. O alfabeto Inglês contém 26 letras, deixando espaço para 32 - 26 = 6 símbolos além das letras. Com este esquema de codificação, você pode ter todas as 26 (um caso) letras em inglês e 6 símbolos (sendo um espaço entre elas).

Descrição do algoritmo

O >>= 5no loop for salta de grupo para grupo, então o grupo de 5 bits fica isolado ANDing o número com a máscara 31₁₀ = 11111₂na frasel & 31

Agora, o código mapeia o valor de 5 bits para o caractere ascii de 7 bits correspondente. Esta é a parte complicada, verifique as representações binárias para as letras do alfabeto em minúsculas na tabela a seguir:

  ascii   |     ascii     |    ascii     |    algorithm
character | decimal value | binary value | 5-bit codification 
--------------------------------------------------------------
  space   |       32      |   0100000    |      11111
    a     |       97      |   1100001    |      00001
    b     |       98      |   1100010    |      00010
    c     |       99      |   1100011    |      00011
    d     |      100      |   1100100    |      00100
    e     |      101      |   1100101    |      00101
    f     |      102      |   1100110    |      00110
    g     |      103      |   1100111    |      00111
    h     |      104      |   1101000    |      01000
    i     |      105      |   1101001    |      01001
    j     |      106      |   1101010    |      01010
    k     |      107      |   1101011    |      01011
    l     |      108      |   1101100    |      01100
    m     |      109      |   1101101    |      01101
    n     |      110      |   1101110    |      01110
    o     |      111      |   1101111    |      01111
    p     |      112      |   1110000    |      10000
    q     |      113      |   1110001    |      10001
    r     |      114      |   1110010    |      10010
    s     |      115      |   1110011    |      10011
    t     |      116      |   1110100    |      10100
    u     |      117      |   1110101    |      10101
    v     |      118      |   1110110    |      10110
    w     |      119      |   1110111    |      10111
    x     |      120      |   1111000    |      11000
    y     |      121      |   1111001    |      11001
    z     |      122      |   1111010    |      11010

Aqui você pode ver que os caracteres ascii que queremos mapear começam com o sétimo e o sexto conjunto de bits ( 11xxxxx₂) (exceto o espaço, que possui apenas o sexto bit), você pode ORcodificar com 5 96( 96₁₀ = 1100000₂) e deve ser o suficiente para fazer o mapeamento, mas isso não funcionaria por espaço (espaço danado!)

Agora sabemos que é preciso tomar cuidado especial para processar o espaço ao mesmo tempo que os outros personagens. Para conseguir isso, o código ativa o sétimo bit (mas não o sexto) no grupo de 5 bits extraído com um OR 64 64₁₀ = 1000000₂( l & 31 | 64).

Até agora, o grupo de 5 bits tem a forma: 10xxxxx₂(o espaço seria 1011111₂ = 95₁₀). Se conseguirmos mapear o espaço para 0não afetar outros valores, podemos ativar o sexto bit e isso deve ser tudo. Aqui está o que a mod 95parte vem a desempenhar, o espaço é 1011111₂ = 95₁₀, usando a operação mod, (l & 31 | 64) % 95)apenas o espaço retorna e 0, depois disso, o código ativa o sexto bit adicionando 32₁₀ = 100000₂ ao resultado anterior, ((l & 31 | 64) % 95) + 32)transformando o valor de 5 bits em um ascii válido personagem

isolates 5 bits --+          +---- takes 'space' (and only 'space') back to 0
                  |          |
                  v          v
               (l & 31 | 64) % 95) + 32
                       ^           ^ 
       turns the       |           |
      7th bit on ------+           +--- turns the 6th bit on

O código a seguir faz o processo inverso, dada uma sequência em minúscula (máximo de 12 caracteres), retorna o valor longo de 64 bits que poderia ser usado com o código do OP:

public class D {
    public static void main(String... args) {
        String v = "hello test";
        int len = Math.min(12, v.length());
        long res = 0L;
        for (int i = 0; i < len; i++) {
            long c = (long) v.charAt(i) & 31;
            res |= ((((31 - c) / 31) * 31) | c) << 5 * i;
        }
        System.out.println(res);
    }
}    
higuaro
fonte
11
Essa resposta não deixa mistério. Pelo contrário, faz o seu pensamento para você.
7
a resposta é ainda mais difícil do que a pergunta: D
Yazan 31/12/14
1
Explicação é muito mais limpo :)
Prashant
40

Adicionando algum valor às respostas acima. O seguinte script groovy imprime valores intermediários.

String getBits(long l) {
return Long.toBinaryString(l).padLeft(8,'0');
}

for (long l = 4946144450195624l; l > 0; l >>= 5){
    println ''
    print String.valueOf(l).toString().padLeft(16,'0')
    print '|'+ getBits((l & 31 ))
    print '|'+ getBits(((l & 31 | 64)))
    print '|'+ getBits(((l & 31 | 64)  % 95))
    print '|'+ getBits(((l & 31 | 64)  % 95 + 32))

    print '|';
    System.out.print((char) (((l & 31 | 64) % 95) + 32));
}

Aqui está

4946144450195624|00001000|01001000|01001000|01101000|h
0154567014068613|00000101|01000101|01000101|01100101|e
0004830219189644|00001100|01001100|01001100|01101100|l
0000150944349676|00001100|01001100|01001100|01101100|l
0000004717010927|00001111|01001111|01001111|01101111|o
0000000147406591|00011111|01011111|00000000|00100000| 
0000000004606455|00010111|01010111|01010111|01110111|w
0000000000143951|00001111|01001111|01001111|01101111|o
0000000000004498|00010010|01010010|01010010|01110010|r
0000000000000140|00001100|01001100|01001100|01101100|l
0000000000000004|00000100|01000100|01000100|01100100|d
Jayan
fonte
26

Interessante!

Os caracteres ASCII padrão visíveis estão no intervalo de 32 a 127.

É por isso que você vê 32 e 95 (127 - 32) lá.

De fato, cada caractere é mapeado para 5 bits aqui (você pode encontrar o que é uma combinação de 5 bits para cada caractere) e, em seguida, todos os bits são concatenados para formar um número grande.

Longs positivos são números de 63 bits, grandes o suficiente para conter a forma criptografada de 12 caracteres. Portanto, é grande o suficiente para reter Hello word, mas para textos maiores você deve usar números maiores, ou mesmo um BigInteger.


Em um aplicativo, queríamos transferir caracteres visíveis em inglês, caracteres persas e símbolos via SMS. Como você vê, existem 32 (number of Persian chars) + 95 (number of English characters and standard visible symbols) = 127valores possíveis, que podem ser representados com 7 bits.

Convertemos cada caractere UTF-8 (16 bits) em 7 bits e obtemos uma taxa de compressão superior a 56%. Assim, poderíamos enviar textos com o dobro do tamanho no mesmo número de SMSs. (É de alguma forma a mesma coisa aconteceu aqui).

Amir Pashazadeh
fonte
Há muito mais acontecendo no código do OP. Por exemplo, isso realmente não explica o que | 64está fazendo.
Ted Hopp
1
@Amir: na verdade, 95 existe porque você precisa obter um caractere de espaço.
Bee
17

Você está obtendo um resultado que é charrepresentação dos valores abaixo

104 -> h
101 -> e
108 -> l
108 -> l
111 -> o
32  -> (space)
119 -> w
111 -> o
114 -> r
108 -> l
100 -> d
Vikas V
fonte
16

Você codificou caracteres como valores de 5 bits e agrupou 11 deles em um comprimento de 64 bits.

(packedValues >> 5*i) & 31 é o i-ésimo valor codificado com um intervalo de 0 a 31.

A parte difícil, como você diz, é codificar o espaço. As letras em inglês em minúsculas ocupam o intervalo contíguo 97-122 em Unicode (e ascii e a maioria das outras codificações), mas o espaço é 32.

Para superar isso, você usou alguma aritmética. ((x+64)%95)+32é quase o mesmo que x + 96(observe como OR bit a bit é equivalente a adição, neste caso), mas quando x = 31, obtemos 32.

Aleksandr Dubinsky
fonte
6

Imprime "olá mundo" por um motivo semelhante:

for (int k=1587463874; k>0; k>>=3)
     System.out.print((char) (100 + Math.pow(2,2*(((k&7^1)-1)>>3 + 1) + (k&7&3)) + 10*((k&7)>>2) + (((k&7)-7)>>3) + 1 - ((-(k&7^5)>>3) + 1)*80));

mas por uma razão um pouco diferente desse:

for (int k=2011378; k>0; k>>=2)
    System.out.print((char) (110 + Math.pow(2,2*(((k^1)-1)>>21 + 1) + (k&3)) - ((k&8192)/8192 + 7.9*(-(k^1964)>>21) - .1*(-((k&35)^35)>>21) + .3*(-((k&120)^120)>>21) + (-((k|7)^7)>>21) + 9.1)*10));
גלעד ברקן
fonte
18
Você deve explicar o que está fazendo, em vez de postar outra charada
Aleksandr Dubinsky
1
Sugiro que você invista algum esforço para encontrar um site (talvez algum Beta StackExchange?) Em que a contribuição de charadas divertidas seja bem-vinda. O Stack Overflow é um site de perguntas e respostas com foco estritamente imposto.
Marko Topolnik
1
@MarkoTopolnik Eu odiaria viver em um mundo em que todas as regras ou o foco fossem tão rigorosamente cumpridos que nunca permitissem exceções. Sem mencionar que existem inúmeras exceções no SO.
você precisa saber é o seguinte
1
Eu também, mas SO é um mundo assim em uma extensão extraordinariamente grande. Claro que existem exceções mesmo aqui, mas elas não são bem-vindas .
Marko Topolnik
1
Outros 15 compartilhavam o sentimento de Alexandr. E você está certo ao apontar que a pergunta em si é inadequada para SO, conforme comentado abaixo.
Marko Topolnik
3

Sem uma Oracleetiqueta, era difícil ver esta pergunta. A recompensa ativa me trouxe aqui. Gostaria que a pergunta também tivesse outras tags de tecnologia relevantes :-(

Eu trabalho principalmente com Oracle database, então eu usaria algum Oracleconhecimento para interpretar e explicar :-)

Vamos converter o número 4946144450195624em binary. Para isso, eu uso um pequeno functionchamado dec2bin, ou seja, decimal para binário .

SQL> CREATE OR REPLACE FUNCTION dec2bin (N in number) RETURN varchar2 IS
  2    binval varchar2(64);
  3    N2     number := N;
  4  BEGIN
  5    while ( N2 > 0 ) loop
  6       binval := mod(N2, 2) || binval;
  7       N2 := trunc( N2 / 2 );
  8    end loop;
  9    return binval;
 10  END dec2bin;
 11  /

Function created.

SQL> show errors
No errors.
SQL>

Vamos usar a função para obter o valor binário -

SQL> SELECT dec2bin(4946144450195624) FROM dual;

DEC2BIN(4946144450195624)
--------------------------------------------------------------------------------
10001100100100111110111111110111101100011000010101000

SQL>

Agora o problema é a 5-bitconversão. Comece a agrupar da direita para a esquerda com 5 dígitos em cada grupo. Nós temos :-

100|01100|10010|01111|10111|11111|01111|01100|01100|00101|01000

Finalmente ficaríamos com apenas 3 dígitos e ele terminaria à direita. Porque, tivemos um total de 53 dígitos na conversão binária.

SQL> SELECT LENGTH(dec2bin(4946144450195624)) FROM dual;

LENGTH(DEC2BIN(4946144450195624))
---------------------------------
                               53

SQL>

hello worldtotal possui 11 caracteres (incluindo espaço), portanto, precisamos adicionar 2 bits ao último grupo em que ficamos com apenas 3 bits após o agrupamento.

Então, agora temos: -

00100|01100|10010|01111|10111|11111|01111|01100|01100|00101|01000

Agora, precisamos convertê-lo para o valor ascii de 7 bits. Para os personagens é fácil, precisamos apenas definir o sexto e o sétimo bit. Adicione 11a cada grupo de 5 bits acima à esquerda.

Isso dá :-

1100100|1101100|1110010|1101111|1110111|1111111|1101111|1101100|1101100|1100101|1101000

Vamos interpretar os valores binários, vou usar binary to decimal conversion function.

SQL> CREATE OR REPLACE FUNCTION bin2dec (binval in char) RETURN number IS
  2    i                 number;
  3    digits            number;
  4    result            number := 0;
  5    current_digit     char(1);
  6    current_digit_dec number;
  7  BEGIN
  8    digits := length(binval);
  9    for i in 1..digits loop
 10       current_digit := SUBSTR(binval, i, 1);
 11       current_digit_dec := to_number(current_digit);
 12       result := (result * 2) + current_digit_dec;
 13    end loop;
 14    return result;
 15  END bin2dec;
 16  /

Function created.

SQL> show errors;
No errors.
SQL>

Vamos olhar para cada valor binário -

SQL> set linesize 1000
SQL>
SQL> SELECT bin2dec('1100100') val,
  2    bin2dec('1101100') val,
  3    bin2dec('1110010') val,
  4    bin2dec('1101111') val,
  5    bin2dec('1110111') val,
  6    bin2dec('1111111') val,
  7    bin2dec('1101111') val,
  8    bin2dec('1101100') val,
  9    bin2dec('1101100') val,
 10    bin2dec('1100101') val,
 11    bin2dec('1101000') val
 12  FROM dual;

       VAL        VAL        VAL        VAL        VAL        VAL        VAL        VAL        VAL     VAL           VAL
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
       100        108        114        111        119        127        111        108        108     101           104

SQL>

Vejamos quais são os personagens: -

SQL> SELECT chr(bin2dec('1100100')) character,
  2    chr(bin2dec('1101100')) character,
  3    chr(bin2dec('1110010')) character,
  4    chr(bin2dec('1101111')) character,
  5    chr(bin2dec('1110111')) character,
  6    chr(bin2dec('1111111')) character,
  7    chr(bin2dec('1101111')) character,
  8    chr(bin2dec('1101100')) character,
  9    chr(bin2dec('1101100')) character,
 10    chr(bin2dec('1100101')) character,
 11    chr(bin2dec('1101000')) character
 12  FROM dual;

CHARACTER CHARACTER CHARACTER CHARACTER CHARACTER CHARACTER CHARACTER CHARACTER CHARACTER CHARACTER CHARACTER
--------- --------- --------- --------- --------- --------- --------- --------- --------- --------- ---------
d         l         r         o         w                  o         l         l         e         h

SQL>

Então, o que obtemos na saída?

dlrow ⌂ olleh

Esse é o olá-mundo ao contrário. A única questão é o espaço . E a razão é bem explicada por @higuaro em sua resposta. Sinceramente, não pude interpretar a questão do espaço na primeira tentativa, até ver a explicação dada em sua resposta.

Lalit Kumar B
fonte
1

Achei o código um pouco mais fácil de entender quando traduzido para PHP, da seguinte maneira:

<?php

$result=0;
$bignum = 4946144450195624;
for (; $bignum > 0; $bignum >>= 5){
    $result = (( $bignum & 31 | 64) % 95) + 32;
    echo chr($result);
}

Ver código ao vivo

slevy1
fonte
0

out.println ((char) (((l & 31 | 64)% 95) + 32/1002439 * 1002439));

Para fazer caps: 3


fonte
1
considere adicionar algumas explicações sobre o que você está fazendo e por quê.
fedorqui 'Então pare de prejudicar'