Votre objectif est de créer une fonction ou un programme pour inverser les bits dans une plage d'entiers étant donné un entier n . En d'autres termes, vous voulez trouver la permutation d'inversion de bits d'une plage de 2 ⁿ éléments, indexés zéro. Il s'agit également de la séquence OEIS A030109 . Ce processus est souvent utilisé dans le calcul de transformées de Fourier rapides, comme l'algorithme Cooley-Tukey sur place pour la FFT. Il existe également un défi pour le calcul de la FFT pour les séquences où la longueur est une puissance de 2.

Ce processus vous oblige à parcourir la plage [0, 2 ⁿ -1] et à convertir chaque valeur en binaire et inverser les bits de cette valeur. Vous traiterez chaque valeur comme un nombre à n chiffres dans la base 2, ce qui signifie que l'inversion ne se produira que parmi les n derniers bits.

Par exemple, si n = 3, la plage d'entiers est [0, 1, 2, 3, 4, 5, 6, 7]. Ceux-ci sont

i  Regular  Bit-Reversed  j
0    000        000       0
1    001        100       4
2    010        010       2
3    011        110       6
4    100        001       1
5    101        101       5
6    110        011       3
7    111        111       7

où chaque index i est converti en un index j en utilisant l'inversion de bits. Cela signifie que la sortie est [0, 4, 2, 6, 1, 5, 3, 7].

Les sorties pour n de 0 à 4 sont

n    Bit-Reversed Permutation
0    [0]
1    [0, 1]
2    [0, 2, 1, 3]
3    [0, 4, 2, 6, 1, 5, 3, 7]

Vous avez peut-être remarqué la formation d'un motif. Étant donné n , vous pouvez prendre la séquence précédente pour n -1 et la doubler. Ensuite, concaténez cette liste doublée à la même liste double mais incrémentée d'une unité. Montrer,

[0, 2, 1, 3] * 2 = [0, 4, 2, 6]
[0, 4, 2, 6] + 1 = [1, 5, 3, 7]
[0, 4, 2, 6] ⊕ [1, 5, 3, 7] = [0, 4, 2, 6, 1, 5, 3, 7]

où ⊕représente la concaténation.

Vous pouvez utiliser l'une des deux méthodes ci-dessus afin de former votre solution. Si vous connaissez un meilleur moyen, vous êtes également libre de l'utiliser. N'importe quelle méthode est correcte tant qu'elle produit les résultats corrects.

Règles

• Il s'agit de code-golf, donc la solution la plus courte l'emporte.
• Les commandes intégrées qui résolvent ce défi dans son ensemble et les commandes intégrées qui calculent l'inversion de bits d'une valeur ne sont pas autorisées. Cela n'inclut pas les commandes intégrées qui effectuent une conversion binaire ou d'autres opérations au niveau du bit.
• Votre solution doit être, au minimum, valable pour n de 0 à 31.

Gelée , 7 6 octets

Ḥ;‘$$¡

Merci à @EriktheOutgolfer d'avoir joué au golf sur 1 octet!

Essayez-le en ligne!

Comment ça marche

Ḥ;‘$$¡  Main link. No arguments.
        Implicit argument / initial return value: 0

     ¡  Read an integer n from STDIN and call the link to the left n times.
    $   Combine the two links to the left into a monadic chain, to be called
        with argument A (initially 0, later an array).
Ḥ         Unhalve; yield 2A.
   $      Combine the two links to the left into a monadic chain, to be called
          with argument 2A.
  ‘         Increment; yield 2A + 1
 ;          Concatenate 2A and 2A + 1.

05AB1E , 8 octets

Code:

¾)IF·D>«

Explication:

¾         # Constant for 0.
 )        # Wrap it up into an array.
  IF      # Do the following input times.
    ·     # Double every element.
     D    # Duplicate it.
      >   # Increment by 1.
       «  # Concatenate the first array.

Utilise l' encodage CP-1252 . Essayez-le en ligne! .

MATL, 13 12 10 9 8 octets

0i:"EtQh

Essayez-le en ligne

Explication

0       % Push number literal 0 to the stack
i:"     % Loop n times
    E   % Multiply by two
    t   % Duplicate
    Q   % Add one
    h   % Horizontally concatenate the result
        % Implicit end of loop, and implicitly display the result

Par souci d'exhaustivité, voici mon ancienne réponse utilisant l'approche non récursive (9 octets).

W:qB2&PXB

Essayez-le en ligne

Explication

W       % Compute 2 to the power% ofImplicitly thegrab input (n) and compute 2^n
:       % Create an array from [1...2^n]
q       % Subtract 1 to get [0...(2^n - 1)]
B       % Convert to binary where each row is the binary representation of a number
2&P     % Flip this 2D array of binary numbers along the second dimension
XB      % Convert binary back to decimal
        % Implicitly display the result

J, 15 11 octets

2&(*,1+*)0:

Il existe une alternative pour 15 octets qui utilise une conversion et une inversion binaires directes.

2|."1&.#:@i.@^]

Usage

   f =: 2&(*,1+*)0:
   f 0
0
   f 1
0 1
   f 2
0 2 1 3
   f 3
0 4 2 6 1 5 3 7
   f 4
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

Explication

2&(*,1+*)0:  Input: n
         0:  The constant 0
2&(     )    Repeat n times starting with x = [0]
2      *       Multiply each in x by 2
     1+        Add 1 to each
    ,          Append that to
2  *           The list formed by multiplying each in x by 2
               Return that as the next value of x
             Return the final value of x

Gelée , 5 octets

2ṗ’UḄ

Essayez-le en ligne!

-1 merci à Dennis .

Haskell , 40 37 octets

f 0=[0]
f a=[(*2),(+1).(*2)]<*>f(a-1)

Essayez-le en ligne!

Merci à @Laikoni pour trois octets!

Octave, 37 octets

@(n)bin2dec(fliplr(dec2bin(0:2^n-1)))

Crée une fonction anonyme nommée ansqui peut simplement être appelée avec ans(n).

Démo en ligne

Python 2, 56 55 54 octets

f=lambda n:[0][n:]or[i+j*2for i in 0,1for j in f(n-1)]

Testez-le sur Ideone .

Merci à @xnor d'avoir joué au golf sur 1 octet!

Java, 422 419 octets:

import java.util.*;class A{static int[]P(int n){int[]U=new int[(int)Math.pow(2,n)];for(int i=0;i<U.length;i++){String Q=new String(Integer.toBinaryString(i));if(Q.length()<n){Q=new String(new char[n-Q.length()]).replace("\0","0")+Q;}U[i]=Integer.parseInt(new StringBuilder(Q).reverse().toString(),2);}return U;}public static void main(String[]a){System.out.print(Arrays.toString(P(new Scanner(System.in).nextInt())));}}

Eh bien, j'ai finalement appris Java pour mon deuxième langage de programmation, donc je voulais utiliser mes nouvelles compétences pour relever un défi simple, et même si cela s'est avéré très long, je ne suis pas déçu. Je suis juste content d'avoir pu relever un simple défi en Java.

Essayez-le en ligne! (Ideone)

Mathematica, 56 33 octets

Le nombre d'octets suppose une source codée ISO 8859-1.

±0={0};±x_:=Join[y=±(x-1)2,y+1]

Cela utilise la définition récursive pour définir un opérateur unaire ±.

Perl, 46 45 octets

Comprend +1 pour -p

Donner le numéro d'entrée sur STDIN

#!/usr/bin/perl -p
map$F[@F]=($_*=2)+1,@F for(@F=0)..$_;$_="@F"

Pyth - 11 octets

ushMByMGQ]0

Suite de tests .

Javascript ES6, 65 53 51 octets

f=(n,m=1)=>n?[...n=f(n-1,m+m),...n.map(i=>i+m)]:[0]

Utilise l'algorithme récursif à double incrémentation.

L'exemple s'exécute:

f(0) => [0]
f(1) => [0, 1]
f(2) => [0, 2, 1, 3]
f(4) => [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

Python 3, 67 59 octets

Merci à @Dennis pour -8 octets

lambda n:[int(bin(i+2**n)[:1:-1],2)//2for i in range(2**n)]

Nous pouvons tout aussi bien avoir une implémentation simple (modifiée) en Python, même si elle est assez longue.

Une fonction anonyme qui prend l'entrée par argument et renvoie la permutation à bits inversés sous forme de liste.

Comment ça marche

lambda n                 Anonymous function with input n
...for i in range(2**n)  Range from 0 to 2**n-1
bin(i+2**n)[:1:-1]       Convert i+2**n to binary string, giving 1 more digit than needed,
                         remove '0b' from start, and reverse
int(...,2)               Convert back to decimal
...//2                   The binary representation of the decimal value has one trailing
                         bit that is not required. This is removed by integer division by 2
:[...]                   Return as list

Essayez-le sur Ideone

Dyalog APL , 12 octets

Requiert ⎕IO←0ce qui est par défaut sur de nombreux systèmes.

2⊥⊖2⊥⍣¯1⍳2*⎕

2⊥ de-base-2 de

⊖ le retourné

2⊥⍣¯1 inverse de la base-2 de

⍳les n premiers entiers, où n est

2* 2 à la puissance de

⎕ entrée numérique

TryAPL en ligne!

À titre de comparaison, voici l'autre méthode:

(2∘×,1+2∘×)⍣⎕⊢0

( le train de fonctions ...

 2∘× deux fois (l'argument)

 , concaténé à

 1+ un plus

 2∘× deux fois (l'argument)

)⍣ appliqué autant de fois que spécifié par

⎕ entrée numérique

⊢ sur

0 zéro

K (ngn / k) , 11 8 octets

2/|!2|&:

Essayez-le en ligne!

 x:3  / just for testing
 &x   / that many zeroes
0 0 0
 2|&x / max with 2
2 2 2
 !x#2 / binary words of length x, as a transposed matrix
(0 0 0 0 1 1 1 1
 0 0 1 1 0 0 1 1
 0 1 0 1 0 1 0 1)
 |!x#2 / reverse
(0 1 0 1 0 1 0 1
 0 0 1 1 0 0 1 1
 0 0 0 0 1 1 1 1)
 2/|!x#2 / base-2 decode the columns
0 4 2 6 1 5 3 7

&est le dernier verbe de la composition, nous avons donc besoin d'un :pour le forcer à être monadique

Julia, 23 22 octets

!n=n>0&&[t=2*!~-n;t+1]

Mise en œuvre plutôt simple du processus décrit dans la spécification de défi.

Essayez-le en ligne!

Pyth, 8 octets

iR2_M^U2

Essayez-le en ligne: démonstration ou suite de tests

Explication:

iR2_M^U2Q   implicit Q (=input number) at the end
     ^U2Q   generate all lists of zeros and ones of length Q in order
   _M       reverse each list
iR2         convert each list to a number

Clojure, 78 octets

Juste en suivant les spécifications ...

(defn f[n](if(= n 0)[0](let[F(map #(* 2 %)(f(dec n)))](concat F(map inc F)))))

Ruby, 57 octets:

->n{(0...a=2**n).map{|x|("%b"%x+=a).reverse[0,n].to_i 2}}

PHP, 57 octets

while($i<1<<$argv[1])echo bindec(strrev(decbin($i++))),_;

prend l'entrée du paramètre de ligne de commande, imprime les valeurs délimitées par des traits de soulignement. Courez avec -nr.

solution récursive, 72 octets

function p($n){$r=[$n];if($n)foreach($r=p($n-1)as$q)$r[]=$q+1;return$r;}

la fonction prend un entier, retourne un tableau

Rubis , 51 octets

f=->n{n<1?[0]:(a=f[n-1].map{|i|i*2})+a.map(&:next)}

Essayez-le en ligne!

Perl 6 , 42 octets

{0,{$^p+^($_-$_/2+>lsb ++$)}...$_}o 1+<*-1

Essayez-le en ligne!

L'incrémentation d'un entier inverse simplement une séquence de bits de poids faible, par exemple de xxxx0111à xxxx1000. Ainsi, le prochain index à bits inversés peut être obtenu à partir du précédent en inversant une séquence de bits les plus significatifs. Le masque XOR peut être calculé avec m - (m >> (ctz(i) + 1))pour m = 2**nou m = 2**n-1.

Perl 6 , 30 octets

my&f={$_&&(^2 X+(f($_-1)X*2))}

Essayez-le en ligne!

Approche récursive.

JavaScript (Firefox 30-57), 48 octets

f=n=>n?[for(x of[0,1])for(y of f(n-1))x+y+y]:[0]

Port de la solution Python 2 de @ Dennis ♦.

Japt , 14 13 octets

2pU Ǥw ú0U Í

Essayez-le en ligne!

Déballé et comment cela fonctionne

2pU o_s2 w ú0U n2

2pU    2**n
o_     range(2**n).map(...)
s2       convert to binary string
w        reverse
ú0U      right-pad to length n, filling with '0'
n2       convert binary string to number

Mise en œuvre simple.

APL (Dyalog Classic) , 9 octets

(⍋,⍨)⍣⎕⊢0

Essayez-le en ligne!

⎕ entrée évaluée

( )⍣⎕⊢0appliquer la chose à ( )plusieurs reprises, en commençant par0

,⍨ concaténer le résultat actuel avec lui-même

⍋ indices d'une permutation tri-ascendante

x86, 31 octets

Prend un suffisamment grand int[] bufferin eaxet n in ecx, et renvoie le tampon danseax .

Implémente l'algorithme de concaténation donné dans l'instruction challenge. Il peut être possible d'économiser des octets en incrémentant les pointeurs de 4 au lieu d'utiliser directement les accès aux tableaux, mais lea/ movest déjà assez court (3 octets pour 3 regs et un multiplicateur).

.section .text
.globl main
main:
        mov     $buf, %eax          # buf addr
        mov     $3, %ecx            # n 

start:
        xor     %ebx, %ebx
        mov     %ebx, (%eax)        # init buf[0] = 0 
        inc     %ebx                # x = 1

l1:
        mov     %ebx, %edi          
        dec     %edi                # i = x-1
        lea     (%eax,%ebx,4), %edx # buf+x 

l2:
        mov     (%eax,%edi,4), %esi # z = buf[i]
        sal     %esi                # z *= 2
        mov     %esi, (%eax,%edi,4) # buf[i] = z
        inc     %esi                # z += 1
        mov     %esi, (%edx,%edi,4) # buf[x+i] = z

        dec     %edi                # --i 
        jns     l2                  # do while (i >= 0)

        sal     %ebx                # x *= 2
        loop    l1                  # do while (--n)

        ret

.data
buf:    .space 256, -1

Hexdump:

00000507  31 db 89 18 43 89 df 4f  8d 14 98 8b 34 b8 d1 e6  |1...C..O....4...|
00000517  89 34 b8 46 89 34 ba 4f  79 f1 d1 e3 e2 e7 c3     |.4.F.4.Oy......|