Dado um número, determine se é um número dobrável.

Um número dobrável é um número tal que, se você pegar a representação binária e "dobrar" ao meio, isso é o resultado da multiplicação XNOR da primeira metade do número e da segunda metade com os dígitos ao contrário, você obterá zero.

Se o número tiver um número ímpar de dígitos em binário, o dígito do meio deverá ser 1 e será ignorado ao dobrar.

Como isso pode ser um pouco confuso, darei alguns exemplos:

178

A representação binária de 178 é

10110010

Para dobrar isso, primeiro dividimos ao meio

1011 0010

Invertemos a segunda metade

1011
0100

E nós não temos as duas metades:

0000

Isso é zero, então esse é um número dobrável.

1644

A representação binária de 1644 é

11001101100

Para dobrar isso, primeiro dividimos ao meio

11001 1 01100

O bit do meio é 1, então jogamos fora.

11001 01100

Invertemos a segunda metade

11001
00110

E nós não temos as duas metades:

00000

Isso é zero, então esse é um número dobrável.

4254

A representação binária de 4254 é

1000010011110

Para dobrar isso, primeiro dividimos ao meio

100001 0 011110

O bit do meio é 0, então esse não é um número dobrável.

Tarefa

Sua tarefa é obter um número positivo e retornar uma verdade se o número estiver dobrando e falso se não estiver. Isso é código de golfe, então tente manter a contagem de bytes baixa.

Casos de teste

Aqui estão os primeiros 99 números dobráveis:

[1, 2, 6, 10, 12, 22, 28, 38, 42, 52, 56, 78, 90, 108, 120, 142, 150, 170, 178, 204, 212, 232, 240, 286, 310, 346, 370, 412, 436, 472, 496, 542, 558, 598, 614, 666, 682, 722, 738, 796, 812, 852, 868, 920, 936, 976, 992, 1086, 1134, 1206, 1254, 1338, 1386, 1458, 1506, 1596, 1644, 1716, 1764, 1848, 1896, 1968, 2016, 2110, 2142, 2222, 2254, 2358, 2390, 2470, 2502, 2618, 2650, 2730, 2762, 2866, 2898, 2978, 3010, 3132, 3164, 3244, 3276, 3380, 3412, 3492, 3524, 3640, 3672, 3752, 3784, 3888, 3920, 4000, 4032, 4222, 4318, 4462, 4558]

Geléia , 9 bytes

Bœs2µḢ^UȦ

Experimente online! ou verifique todos os casos de teste .

Como funciona

Bœs2µḢ^UȦ  Main link. Argument: n

B          Binary; convert n to base 2.
 œs2       Evenly split 2; split the base 2 array into chunks of equal-ish length.
           For an odd amount of digits, the middle digit will form part of the
           first chunk.
    µ      Begin a new, monadic chain. Argument: [A, B] (first and second half)
     Ḣ     Head; remove and yield A.
       U   Upend; reverse the digits in [B].
      ^    Perform vectorized bitwise XOR of the results to both sides.
           If A is longer than B, the last digit will remain untouched.
           n is a folding number iff the result contains only 1's.
        Ȧ  Octave-style all; yield 1 iff the result does not contain a 0.

05AB1E , 13 12 bytes

Código:

bS2ä`R0¸«s^P

Usa o CP-1252 codificação . Experimente online!

Explicação:

Primeiro, convertemos o número em binário usando b. 1644 torna-se 11001101100 . Dividimos isso em dois pedaços com 2ä. Por exemplo, 11001101100 se tornaria:

[1, 1, 0, 0, 1, 1]
[0, 1, 1, 0, 0]

Se houver um número desigual de bits, a primeira parte receberá o bit extra. Nós Rinvertemos a última string e adicionamos um zero usando 0¸«. A razão para isso é fornecer apenas resultados de verdade quando o bit do meio for 1 ( 1 XOR 0 = 1 e 0 XOR 0 = 0 ). Se não houver um bit do meio, o 05AB1E ignorará o último bit (o zero que foi anexado):

[1, 1, 0, 0, 1, 1]
[0, 0, 1, 1, 0, 0]

A última coisa que precisamos fazer é fazer um XOR em elementos e pegar o produto do resultado. Se houver um elemento em excesso, o programa deixará o último elemento de fora ( [1, 0, 0] XOR [0, 1] = [1, 1]). Por exemplo:

[1, 1, 0, 0, 1, 1]
[0, 0, 1, 1, 0, 0] XOR

Torna-se:

[1, 1, 1, 1, 1, 1]

E o produto disso é 1 , que é verdade.

Java 7, 152 145 142 138 134 bytes

boolean f(Long a){byte[]b=a.toString(a,2).getBytes();int i=0,l=b.length,z=l%2<1?1:b[l/2]-48;for(;i<l/2;)z*=b[i]-b[l-++i];return z!=0;}

Laços sobre a corda como faria em um palíndromo, procurando zeros. Mantém o controle multiplicando repetidamente, então tudo que você precisa fazer é verificar se não é zero no final.

Sem barras de rolagem:

boolean f(Long a){
    byte[]b=a.toString(a,2).getBytes();
    int i=0,l=b.length,z=l%2<1?1:b[l/2]-48;
    for(;i<l/2;)
        z*=b[i]-b[l-++i];
    return z!=0;
}

JavaScript (ES6), 61 57 52 bytes

Computa recursivamente:

(bit(N) XOR bit(0)) AND (bit(N-1) XOR bit(1)) AND (bit(N-2) XOR bit(2)) etc.

onde Né a classificação do bit mais alto definido na entrada.

Se a entrada tiver um número ímpar de bits, o bit do meio será XOR com indefinido (o valor retornado por pop()uma matriz vazia), o que o deixará inalterado. Portanto, um 0bit do meio apaga a saída e um 1bit do meio não altera o resultado de outras operações - o que é consistente com a definição de desafio de um número dobrável.

f=(n,[a,...b]=n.toString(2))=>a?(a^b.pop())&f(n,b):1

// testing integers in [1 .. 99]
for(var i = 1; i < 100; i++) {
  f(i) && console.log(i);
}

Python 2, 57 bytes

s=bin(input())[2:]
while''<s!='1':s[-1]==s[0]<_;s=s[1:-1]

Saídas via código de saída : erro para Falsey e nenhum erro para Truthy.

Converte a entrada em binário. Verifica se o primeiro e o último caractere são desiguais, mantém e repete isso após remover esses caracteres.

A comparação s[-1]==s[0]<_gera um erro se o primeiro e o último caractere forem desiguais, tentando avaliar a variável não atribuída denominada _. Se são iguais, a cadeia de desigualdades é em curto-circuito. Quando chegamos ao elemento do meio de 1, o whileloop é encerrado para um caso especial como OK.

Suspeito que uma abordagem puramente aritmética seja mais curta com uma recursão semelhante f=lambda n,r=0:...f(n/2,2*r+~n%2)...a digitar dígitos binários do final invertido e invertido, e detectar quando ne rsão iguais a um centro 1. Existem sutilezas, porém, com zeros à esquerda e o centro.

Python 2, 94 79 72 67 bytes

F=lambda s:s in'1'or(s[0]!=s[-1])*F(s[1:-1])
lambda n:F(bin(n)[2:])

Guardado 12 bytes graças a @xnor

Define uma função sem nome na segunda linha.

Explicação (com algum espaço em branco adicionado):

F = lambda s:                                        # We define a function, F, which takes one argument, the string s, which returns the following:
             s in'1'                                 # Gives true if s is '' or s is '1', the first case is a base case and the second is for the middle bit case.
                     or(s[0] != s[-1])               # Or the first and last are different
                                      * F(s[1:-1])   # And check if s, without the first and last element is also foldable.
lambda n: F(bin(n)[:-2])                             # The main function, which calls F with the argument in binary form.

Experimente aqui!

Haskell, 89 88 86 bytes

f n|n<2=[n]|1>0=mod n 2:f(div n 2)
g n=elem(product$zipWith(+)(f n)$reverse$f n)[1,2]

Funciona somando bit a representação de bits com seu reverso e obtendo o produto. Se for 1 ou 2, o número é um número dobrável (1 se houver bits pares que dobram, 2 se houver bits ímpares e um no meio).

Python 2, 100 99 95 94 bytes

Parece um pouco longo, mas continuarei trabalhando :) Imprime a 1se o número puder ser dobrado, 0caso contrário.

a=bin(input())[2:]
b=len(a)
print(a[b/2]>=`b%2`)*all(c!=d for c,d in zip(a[:b/2],a[:~b/2:-1]))

^{Teste aqui!}

^{graças ao Assistente de trigo para salvar 1 byte :)}

^{graças a Rod pela economia de 5 bytes! :)}

> <> , 37 + 3 = 40 bytes

<,2-@:%2:v!?:
=2lrv?=1l<+={$r0?
0=n;>

A entrada deve estar presente na pilha no início do programa, portanto, +3 bytes para o -v sinalizador.

Experimente online!

Gelatina , 13 bytes

Bœs2U0¦z0^/€Ạ

TryItOnline
Ou termos correspondentes até 4558

Quão?

Bœs2U0¦z0^/€Ạ - Main link: n
B             - binary
 œs2          - split into 2 slices (odd length will have first longer than second)
     0¦       - apply to index 0 (the right hand one)
    U         - reverse
       z0     - zip together with filler 0 (thus central 1 or 0 will pair with 0)
          /€  - reduce with for each
         ^    -     XOR
            Ạ - All truthy?

Perl, 46 bytes

Inclui +1 para -p

Corra com o número em STDIN

folding.pl <<< 178

folding.pl:

#!/usr/bin/perl -p
$_=($_=sprintf"%b",$_)<s%.%!/\G1$/^$&^chop%eg

Eu considero um bug perl que isso até funcione. Interno $_não deve estar recebendo atualizações de posição de correspondência depois de modificado. Neste programa, a posição da partida realmente ultrapassa o final de$_

Braquilog , 16 bytes

ḃḍ{↔|h1&b↔}ᵗz₂≠ᵐ

Não funciona muito bem online ...

Recebe a entrada pela variável de entrada e sai por sucesso ou falha. Ele depende muito z₂, que está no idioma desde 30 de abril, mas esquecemos de pedir para que o TIO seja usado. Por enquanto, isso só funciona em uma instalação local do idioma. De qualquer forma, é provavelmente uma abordagem excessivamente ingênua.

                    The input
ḃ                   's binary representation
 ḍ                  split in half
  {       }ᵗ        with its second half
   ↔|               either reversed, or
     h1             if it starts with 1
       &b           relieved of its first element
         ↔          and then reversed
              ≠     has no duplicate elements
            z  ᵐ    in any pair of elements zipped from the two halves
             ₂      which are equal in length.

Brachylog (no TIO), 19 bytes

ḃḍ{↔|h1&b↔}ᵗlᵛ↖Lz≠ᵐ

Experimente online!

lᵛ↖Lzé funcionalmente equivalente a z₂(se você não usar a variável L em nenhum outro lugar), mas também terá três bytes a mais.

Python 2, 76 71 69 bytes

-5 bytes graças a @Dennis ( ''está presente em '1', então substitua in('','1')por in'1')
-2 bytes graças a @xnor (use multiplicação, (...)*no lugar de and)

f=lambda n:f(bin(n)[2:])if n<''else n in'1'or(n[0]!=n[-1])*f(n[1:-1])

Ideone

A função recursiva, na primeira chamada, né um número; portanto, ela é avaliada como menor que a sequência vazia, com if n<'', e a função é chamada novamente, mas com nconversão para uma sequência binária; a cauda é uma string vazia (mesmo comprimento de bit) ou a do meio, que retorna true para empty ou a '1'; no caminho para baixo, ele testa desigualdade nos bits externos (equivalente a XOR) e retorna nos bits internos n[1:-1].

Python 2, 63 bytes

s=bin(input())[2:]
while s[0]!=s[-1]:s=s[1:-1]or'1'
print'1'==s

Imprime Trueou False. Assume a representação binária se remove repetidamente o primeiro e o último caracteres, desde que sejam desiguais. Verifica se o que resta é a cadeia vazia ou uma central 1. Isto é feito através da conversão ''para '1'e verificar se o resultado for igual '1', que também evitar um erro de índice na string vazia.

PowerShell v2 +, 143 bytes

Duas abordagens possíveis, ambas com a mesma contagem de bytes.

Método 1:

param($n)if($n-eq1){$n++}$o=1;0..(($b=($n=[convert]::ToString($n,2)).length-1)/2-!($b%2))|%{$o*=$n[$_]-ne$n[$b-$_]};$o*(+"$($n[$b/2])",1)[$b%2]

Recebe entrada $n, se for -eqnecessário 1(um caso especial para esse algoritmo), aumente. Defina $output como 1(ou seja, assuma a verdade) e, em seguida, faça um loop do 0ponto intermediário do número de entrada que foi [convert]editado para binário. Note o-!($b%2) conta para números binários de comprimento ímpar.

A cada iteração, comparamos o dígito atual $n[$_]com o dígito do mesmo tamanho do final $n[$b-$_]e multiplicamos o resultado booleano em $o(essencialmente executando um -andem todos eles). Depois que o loop é concluído, precisamos levar em consideração o dígito binário médio, que é o pseudo-ternário no final (array indexado via $b%2). Isso 1ou 0é deixado no gasoduto, ea saída está implícita.

Método 2:

param($n)for($n=[convert]::ToString($n,2);$n.Length-gt2){if($n[0]-ne$n[-1]){$n=$n[1..($n.Length-2)]}else{0;exit}}($n-join'+'|iex)-eq1-or$n-eq10

Leva a entrada e faz o mesmo processo ao [convert]número para binário. Então estamos em um forloop desde que o .lengthda cadeia binária seja -greatert han 2. Quando estamos no circuito, se os primeiros $n[0]e últimos $n[-1]dígitos são -not equa, cortar esses dois dígitos fora $ne re store-lo em $n. Caso contrário, saída 0e exit. Uma vez que estamos fora do circuito, ou temos (uma matriz de 1, 1,0, 0,1, 1,1, ou 0,0), ou a cadeia binária para dois 10, ou três 11. Então, precisamos testar essas duas possibilidades. Pela primeira vez, -join $njuntos, +avaliamos o resultado e testamos que é1(isto é verdade para matrizes 1, 1,0e 0,1, mas é e$falsepara matrizes ou strings ou ). A outra metade está testando se é ual para (isto é, entrada de ). Esse booleano é deixado no pipeline e a saída é implícita.0,01,11011-or$n-eq102

CJam , 13 bytes

ri2b_W%.+:*3&

Experimente online! ou gere uma lista de números dobráveis ​​até um determinado número.

ri2b   e# convert input to binary
_W%.+  e# flip and sum (if folding all bits are 1 except middle)
:*     e# product is 0 or power of 2 (2 if middle folds)
3&     e# keep only 1 or 2, everything else becomes 0 (false)

MATL , 16 bytes

tBn2/kW&\hBZ}P=~

Verdade é uma matriz com todos os. Verifique os critérios de verdade / falsidade aqui .

Experimente online! Ou Verifique os 20 primeiros casos de teste .

Explicação

Vamos usar a entrada 1644como um exemplo.

t     % Imolicitly take input. Duplicate
      %   STACK: 1644, 1644
Bn    % Number of digits of binary expansion
      %   STACK: 1644, 11
2/k   % Divide by 2 and round down
      %   STACK: 1644, 5
W     % 2 raised to that
      %   STACK: 1644, 32
&\    % Divmod
      %   STACK: 12, 51
h     % Concatenate horizontally
      %   STACK: [12 51]
B     % Binary expansion. Each numnber gives a row, left-padded with zeros if needed
      %   STACK: [0 0 1 1 0 0; 1 1 0 0 1 1]
Z}    % Split into rows
      %   STACK: [0 0 1 1 0 0], [1 1 0 0 1 1]
P     % Reverse
      %   STACK: [0 0 1 1 0 0], [1 1 0 0 1 1]
=~    % True for entries that have different elements
      %   STACK: [1 1 1 1 1 1]
      % Implicitly display

PHP, 101 bytes

for($r=1;$i<($l=strlen($b=decbin($argv[1])))>>1;)$r*=$b[$i]^1^$b[$l-++$i]^1;$r*=$l%2?$b[$i]:1;echo$r;

ou com log

for($r=1,$s=log($n=$argv[1],2)^0;2*$i<$s;)$r*=($n>>$i)%2^($n>>$s-$i++)%2;$s%2?:$r*=($n>>$i)%2;echo$r;

108 bytes com matriz

for($r=1,$a=str_split(decbin($argv[1]));$a;)$r*=array_pop($a)!=($a?array_shift($a):0);$r*=$a?$a[0]:1;echo$r;

Valores verdadeiros <10000

1,2,6,10,12,22,28,38,42,52,56,78,90,108,120,142,150,170,178,204,212,232,240,286,310,346,370,412,436,472,496,542,558,598,614,666,682,722,738,796,812,852,868,920,936,976,992,1086,1134,1206,1254,1338,1386,1458,1506,1596,1644,1716,1764,1848,1896,1968,2016,2110,2142,2222,2254,2358,2390,2470,2502,2618,2650,2730,2762,2866,2898,2978,3010,3132,3164,3244,3276,3380,3412,3492,3524,3640,3672,3752,3784,3888,3920,4000,4032,4222,4318,4462,4558,4726,4822,4966,5062,5242,5338,5482,5578,5746,5842,5986,6082,6268,6364,6508,6604,6772,6868,7012,7108,7288,7384,7528,7624,7792,7888,8032,8128,8318,8382,8542,8606,8814,8878,9038,9102,9334,9398,9558,9622,9830,9894

Julia , 66 bytes

c(s)=s==""||s=="1"||(s[1]!=s[end]&&c(s[2:end-1]))
f(x)=c(bin(x))

Meu primeiro golfe! funciona da mesma maneira que a solução Python do mesmo tamanho, pequenas diferenças devido à linguagem (embora eu tenha inventado por conta própria ...).

Explicação:

c(s) = s == "" || # Base case, we compared all the digits from 
                  # both halves.
       s == "1" || # We compared everything but left a 1 in the middle
       (s[1] != s[end] &&  # First digit neq last digit (XNOR gives 0).
        c(s[2:end-1]))     # AND the XNOR condition is satisfied for the  
                           # 2nd to 2nd to last digit substring.
f(x) = c(bin(x))  # Instead of a string f takes an integer now.

C, 223 201 189 194 178 Bytes

i,j,m,l,r;f(n){for(m=j=1,i=n;i/=2;++j);for(l=r=i=0;i<j/2;i++)r|=n&m?1<<j/2-i-1:0,m*=2;i=(j&1&&n&m)?i+1:(j&1)?l=r:i;n>>=i;for(m=1;i<j;i++)l|=n&m,m*=2;return !(~(l^r)&(1<<j/2)-1);}

Algoritmo de força bruta. Vamos ver até onde ele pode ser jogado.

Melhores correções de configuração de teste ...

 main()
 {
    int t, s, u, testSet[] = 
    {
    1, 2, 6, 10, 12, 22, 28, 38, 42, 52, 56, 78, 90, 108, 120,
    142, 150, 170, 178, 204, 212, 232, 240, 286, 310, 346, 370,
    412, 436, 472, 496, 542, 558, 598, 614, 666, 682, 722, 738,
    796, 812, 852, 868, 920, 936, 976, 992, 1086, 1134, 1206,
    1254, 1338, 1386, 1458, 1506, 1596, 1644, 1716, 1764, 1848,
    1896, 1968, 2016, 2110, 2142, 2222, 2254, 2358, 2390, 2470,
    2502, 2618, 2650, 2730, 2762, 2866, 2898, 2978, 3010, 3132,
    3164, 3244, 3276, 3380, 3412, 3492, 3524, 3640, 3672, 3752,
    3784, 3888, 3920, 4000, 4032, 4222, 4318, 4462, 4558
    };


    for (u=s=0,t=1;t<=4558;t++)
    {
        if (f(t))
        {
          u++;            
          if (testSet[s++]!=t)
              printf("BAD VALUE %d %d\n", testSet[s-1], t);
        }
    }

    printf("%d == %d Success\n", u,
           sizeof(testSet)/sizeof(testSet[0]));

}

MATL , 13 bytes

BttP=<~5Ms2<*

Verdade é uma matriz com todos os. Verifique os critérios de verdade / falsidade aqui .

Experimente online! Ou verifique os 20 primeiros casos de teste .

Explicação

Usando a entrada 1644como um exemplo:

B     % Implicit input. Convert to binary
      %   STACK: [1 1 0 0 1 1 0 1 1 0 0]
t     % Duplicate
      %   STACK: [1 1 0 0 1 1 0 1 1 0 0], [1 1 0 0 1 1 0 1 1 0 0]
tP=   % Element-wise compare each entry with that of the reversed array
      %   STACK: [1 1 0 0 1 1 0 1 1 0 0], [0 0 0 0 0 1 0 0 0 0 0]
<~    % True (1) if matching entries are equal or greater
      %   STACK: [1 1 1 1 1 1 1 1 1 1 1]
5M    % Push array of equality comparisons again
      %   STACK: [1 1 1 1 1 1 1 1 1 1 1], [0 0 0 0 0 1 0 0 0 0 0]
s     % Sum of array
      %   STACK: [1 1 1 1 1 1 1 1 1 1 1], 1
2<    % True (1) if less than 2
      %   STACK: [1 1 1 1 1 1 1 1 1 1 1], 1
*     % Multiply
      %   STACK: [1 1 1 1 1 1 1 1 1 1 1]
      % Implicitly display

JavaScript, 71 bytes

(i,n=i.toString(2))=>/^(1*)2?\1$/.test(+n+ +n.split``.reverse().join``)

Define uma função anônima.

Este método pode não ser o mais curto, mas, tanto quanto eu sei, é único. Ele adiciona o número em binário a si mesmo invertido, tratando-o como decimal e, em seguida, verificando se o resultado é válido usando uma expressão regular.

Retina, 92 bytes

A contagem de bytes assume a codificação ISO 8859-1.

.+
$*
+`(1+)\1
${1}0
01
1
^((.)*?)1??((?<-2>.)*$.*)
$1¶$3
O$^`.(?=.*¶)

T`01`10`^.*
^(.*)¶\1

Experimente online

Converta para unário. Converta isso em binário. Corte o número ao meio e remova o meio, 1se houver. Inverta a primeira metade. Troque seus uns e zeros. Combine se as duas metades forem iguais.

Retina, 71 70 60 bytes

.+
$*
+`^(1*)\1(1?)\b
$1 $.2
+`^ (.)(.*) (?!\1).$
$2
^( 1)?$

Provavelmente ainda tenho muito a aprender sobre Retina (por exemplo, regex recursivo?). Explicação: A etapa 1 converte de decimal em unário. A etapa 2 converte de unário para pseudo-binário. A etapa 3 remove os dígitos das duas extremidades, desde que sejam incompatíveis. A etapa quatro corresponde a uma central final opcional 1, se necessário. Editar: salvou 1 byte graças a @ mbomb007. Economizei 10 bytes melhorando minha conversão unária em binária.

Python 2, 61 59 bytes

Salvando dois bytes para converter turnos em multiplicações

m=n=input()
i=0
while m:i*=2;i+=m&1;m/=2
print(n+i+1)&(n+i)

Retorna 0para um número dobrável e qualquer outra coisa para não dobrar. Usa a abordagem de manipulação de bits.

C, 65 63 bytes

Dois bytes para converter turnos em multiplicações

i,m;
f(n){
 m=n;i=0;
 while(m)i*=2,i+=m&1,m/=2;
 return(n+i+1)&(n+i);
}

O espaço em branco já está excluído do bytecount, retorna 0 para um número dobrável e qualquer outra coisa para não dobrar. Usa a abordagem de manipulação de bits.

k, 77 bytes

{X:2 0N#X@&:|\X:0b\:x;c:#:'X;$[(~*X 1)|(=). c;~|/(=).(::;|:)@'(-&/ c)#'X;0b]}

a título de explicação, uma tradução para q

{X:2 0N#X where maxs X:0b vs x;
  c:count each X;
  $[(not first last X)or(=). c;
    not any(=).(::;reverse)@'(neg min c)#'X;0b]
  };