Séquence flottante de bits

22

Un bit flotte du LSB au MSB se déplaçant d'une position à chaque fois jusqu'à ce qu'il flotte vers le haut du conteneur:

0000
0001
0010
0100
1000

Une fois qu'un bit flotte vers le haut, un autre bit commence son voyage et s'arrête lorsqu'il rencontre un autre bit:

1001
1010
1100

Cela se produit jusqu'à ce que le conteneur soit rempli de bits:

1101
1110
1111

Défi

Étant donné un nombre entier, sortez la " séquence flottante de bits " pour un conteneur de ce nombre de bits.

  • Chaque terme de la séquence peut être séparé par n'importe quel séparateur de votre choix.
  • Modifier : séquence doit être affichée en tant que nombres entiers décimal, en commençant par le premier therm: 0.
  • La taille du conteneur doit être supérieure à zéro et jusqu'au nombre de bits du plus grand entier pris en charge par la langue de votre choix. Vous pouvez supposer que l'entrée correspond toujours à cette exigence.

Exemples

Seule la séquence numérique est requise, la représentation binaire est montrée comme exemple:

  • Pour 1 :0 1

    0 -> 0
    1 -> 1
    
  • Pour 3 :0 1 2 4 5 6 7

    000 -> 0
    001 -> 1
    010 -> 2
    100 -> 4
    101 -> 5
    110 -> 6
    111 -> 7
    
  • Pour 4 :0 1 2 4 8 9 10 12 13 14 15

    0000 -> 0
    0001 -> 1
    0010 -> 2
    0100 -> 4
    1000 -> 8
    1001 -> 9
    1010 -> 10
    1100 -> 12
    1101 -> 13
    1110 -> 14
    1111 -> 15
    
  • Pour 8 :0 1 2 4 8 16 32 64 128 129 130 132 136 144 160 192 193 194 196 200 208 224 225 226 228 232 240 241 242 244 248 249 250 252 253 254 255

    00000000 -> 0
    00000001 -> 1
    00000010 -> 2
    00000100 -> 4
    00001000 -> 8
    …
    …
    …
    11111000 -> 248
    11111001 -> 249
    11111010 -> 250
    11111100 -> 252
    11111101 -> 253
    11111110 -> 254
    11111111 -> 255
    
PaperBirdMaster
la source
2
Pouvons-nous produire la séquence dans n'importe quel ordre (c'est-à-dire inversé), ou doivent-ils être triés du plus bas au plus élevé?
Kevin Cruijssen
1
Pouvons-nous sortir sous forme de flotteurs? Par exemple[0.0, 1.0]
Grimmy
8
Pouvons-nous produire en utilisant la représentation binaire?
Neil
Pouvons-nous sortir la séquence indexée zéro? soit0 -> [0, 1]
attinat

Réponses:

7

05AB1E , 10 octets

LRL˜Íoî.¥ï

Essayez-le en ligne!

L                 # range [1..input]
 R                # reversed
  L               # convert each to a range: [[1..input], [1..input-1], ..., [1]]
   ˜              # flatten
    Í             # subtract 2 from each
     o            # 2**each
      î           # round up (returns a float)
       ï          # convert to integer
        .¥        # undelta
Grimmy
la source
2
Je pense qu'il y a un méta-post quelque part autorisant les flottants avec .0par défaut pour les entiers, mais pas sûr. Personnellement, je mets généralement ïle pied de page en jolie impression et ne l'inclue pas dans le nombre d'octets.
Kevin Cruijssen
7

Python 2 , 45 octets

y=n=2**input()
while y:print n-y;y=y&y-1or~-y

Essayez-le en ligne!

Il s'avère plus court pour générer 2**nmoins chaque terme dans la séquence d'entrée n. Si nous regardons leur expansion binaire, ci-dessous pour n=5, nous voyons un joli motif de triangles de 1 dans les extensions binaires.

100000  32
011111  31
011110  30
011100  28
011000  24
010000  16
001111  15
001110  14
001100  12
001000  8
000111  7
000110  6
000100  4
000011  3
000010  2
000001  1

Chaque nombre est obtenu à partir du précédent en supprimant le plus à droite dans l'expansion binaire, sauf si cela ferait le nombre 0, nous soustrayons 1 à la place, créant un nouveau bloc de 1 qui commence un nouveau triangle plus petit. Ceci est implémenté comme y=y&y-1or~-y, où y&y-1est un petit truc pour supprimer le 1 le plus à droite, et or~-ydonne à la y-1place si cette valeur était 0.

Python 2 , 49 octets

def f(n,x=0):1%n;print x;f(n-x%2,x+(x%2**n or 1))

Essayez-le en ligne!

Une fonction qui s'imprime, se terminant par une erreur. Le programme plus agréable ci-dessous s'est avéré plus long.

51 octets

n=input()
x=0
while n:n-=x%2;print x;x+=x%2**n or 1

Essayez-le en ligne!

xnor
la source
6

Gelée , 11 10 octets

RUḶ’F2*ĊÄŻ

Port de @Grimy réponse 05AB1E de , alors assurez - vous de le upvote!
-1 octet grâce à @Grimy .

Essayez-le en ligne.

Explication:

R           # Create a list in the range [1, (implicit) argument]
 U          # Reverse it to [argument, 1]
           # Create an inner list in the range [0, N) for each value N in this list
           # Decrease each by 1
    F       # Flatten the list of lists
     2*     # Take 2 to the power each
       Ċ    # Ceil
        Ä   # Undelta (cumulative sum) the list
         Ż  # And add a leading 0
            # (after which the result is output implicitly)
Kevin Cruijssen
la source
2
R_2-> Ḷ’pour -1. est la seule gamme sensée , je souhaite vraiment que 05AB1E ait un seul octet pour cela.
Grimmy
@Grimy Ah, comment ai-je raté celui-là. J'ai recherché la plage et j'ai dû l'ignorer d'une manière ou d'une autre ..>.> Merci!
Kevin Cruijssen
4

Perl 5 ( -n), 41 40 octets

-1 octet à Xcali

map{/01.*1/||say oct}glob"0b"."{0,1}"x$_

TIO

  • "{0,1}"x$_: la chaîne "{0,1}"répétée n fois
  • "0b". : concaténer à "0b"
  • glob : expansion globale (produit cartésien)
  • map{... }: pour chaque élément
  • /01.*1/||: sauter quand 01suivi de quelque chose1
  • say oct : pour convertir en décimal et dire
Nahuel Fouilleul
la source
40
Xcali
4

JavaScript (ES6), 43 octets

En cas de doute, utilisez la méthode xnor .

n=>(g=x=>x?[n-x,...g(x&--x||x)]:[])(n=1<<n)

Essayez-le en ligne!


JavaScript (ES6),  59 57 55  52 octets

f=(n,x=0)=>x>>n?[]:[x,...f(n,x+=x+(x&=-x)>>n|!x||x)]

Essayez-le en ligne!

Comment?

p(X)2Xp(0)=0

xx1x

p(52)=52AND52=4

panan(0)=0

an(k+1)={an(k)+p(an(k)),if p(an(k))0 and an(k)+p(an(k))<2nan(k)+1,autrement

Commenté

f = (                   // f is a recursive function taking:
  n,                    //   n = input
  x = 0                 //   x = current term of the sequence
) =>                    //
  x >> n ?              // if x is greater than or equal to 2**n:
    []                  //   stop recursion
  :                     // else:
    [                   //   update the sequence:
      x,                //     append the current term to the sequence
      ...f(             //     do a recursive call:
        n,              //       pass n unchanged
        x +=            //       update x:
          x + (x &= -x) //         given x' = lowest bit of x set to 1:
          >> n          //         if x + x' is greater than or equal to 2**n
          | !x          //         or x' is equal to 0: add 1 to x
          || x          //         otherwise, add x' to x
      )                 //     end of recursive call
    ]                   //   end of sequence update
Arnauld
la source
3

Python 2 , 95 76 octets

n=input()
a=0
print 0
while n:
 for j in range(n):print a+2**j
 n-=1;a+=2**n

Essayez-le en ligne!

TFeld
la source
3

Perl 6 , 43 octets

{0 x$_,{say :2($_);S/(0)1|0$/1$0/}...1 x$_}

Essayez-le en ligne!

Bloc de code anonyme qui prend un nombre et génère la séquence séparée par des retours à la ligne. Cela fonctionne en commençant par 0 répété n fois, puis en remplaçant soit 01par 10ou le dernier 0par a 1jusqu'à ce que le nombre soit juste un.

Ou 40 octets, selon l'approche de Nahuel Fouilleul

{grep /010*1/|{say :2($_)},[X~] ^2 xx$_}

Essayez-le en ligne!

Jo King
la source
" puis en remplaçant soit 01par 10ou le dernier 0par un 1jusqu'à ce que le nombre soit juste " C'est un coup de génie!
PaperBirdMaster
2

05AB1E , 13 12 octets

Tsãʒ1ÛSO2‹}C{

-1 octet grâce à @Grimy ( également un œil à son approche plus courte ici).

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

T             # Push 10
 sã           # Swap to get the (implicit) input, and get the cartesian product with "10"
   ʒ          # Filter it by:
    1Û        #  Remove leading 1s
      SO      #  Get the sum of the remaining digits
        !     #  Check that the sum is either 0 or 1 by taking the factorial
              #  (NOTE: Only 1 is truthy in 05AB1E)
         }C   # After the filter: convert all remaining strings from binary to integer
           {  # And sort (reverse) them
              # (after which the result is output implicitly)
Kevin Cruijssen
la source
Autre 13: oL<ʒbIj1Û1¢2‹. Il ne semble pas que je puisse le faire baisser.
Grimmy
1
@Grimy Je viens d'avoir oL<ʒbIj1ÛSO2‹et essayais de voir où était mon erreur. :) Mais je suis heureux de voir que vous n'êtes pas en mesure de trouver une version plus courte pour l'une de mes réponses pour un changement. ; p (inb4 vous en trouvez un plus court après tout xD)
Kevin Cruijssen
1
@Grimy j'ai le sentiment SO2‹ peut être en quelque sorte 3 octets, mais je ne le vois pas et je ne suis pas tout à fait sûr. Il existe des alternatives, commeSO1~ ou SÆ>d, mais je ne trouve pas de 3 octets.
Kevin Cruijssen
1
dix avec une approche complètement différente
Grimmy
1
Votre sentiment était juste, je viens de trouver un 3-byter: SO!. Je suis sûr que j'ai d'anciennes réponses à utiliser 2‹qui pourraient également en bénéficier.
Grimmy
2

Rétine , 26 octets

.+
*0
L$w`.(.*)
$.`*1$'1$1

Essayez-le en ligne! Sorties en binaire. Si ce n'est pas acceptable, alors pour 39 octets:

.+
*0
L$w`.(.*)
$.`*1$'1$1
+`10
011
%`1

Essayez-le en ligne! Explication:

.+
*0

Convertissez l'entrée en une chaîne de nzéros.

L$w`.(.*)

Correspond à toutes les sous-chaînes non vides possibles.

$.`*1$'1$1

Pour chaque sous-chaîne, sortez: le préfixe avec 0 s changé en1 s; le suffixe; la correspondance avec l'initiale a été 0remplacée par 1.

+`10
011
%`1

Convertissez du binaire en décimal.

Neil
la source
2

Brachylog , 27 octets

1;0|⟦₅;2z^₍ᵐLtT&-₁↰+ᵐ↙T,L,0

Essayez-le en ligne!

Sorties hors service et avec doublons. Si ce n'est pas correct, virez doà la fin.

Chaîne indépendante
la source
1

Fusain , 19 octets

I⮌E⊕θEι⁺⁻X²IθX²ιX²λ

Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication:

    θ               Input
   ⊕                Incremented
  E                 Map over implicit range
      ι             Outer index
     E              Map over implicit range
           Iθ       Input cast to integer
               ι    Outer index
                  λ Inner index
         X²  X² X²  Power of 2
       ⁺⁻           Subtract and add
 ⮌                  Reverse outer list
I                   Cast to string
                    Implicitly print
Neil
la source
1

Rétine , 24 octets

.+
*0
/0/+<0`(0)1|0$
1$1

Sorties en binaire. L'entrée doit avoir une nouvelle ligne de fin.

Tentative d'explication:

.+              #match the entire input
*0              #replace it with that many zeroes
/0/+<0`(0)1|0$  #while the string has a 0, substitute the first match and output
1$1             #if 01 is present in the string, replace it with 10, else replace the last character with $

J'ai essayé d'éviter les 3 octets de long /0/ option regex en réorganisant les options, mais pas pu.

Essayez-le en ligne!

mon pronom est monicareinstate
la source
Je ne pense pas que la sortie en binaire soit autorisée. Il y a un commentaire demandant si c'est autorisé, mais il vaut mieux supposer que vous ne pouvez pas jusqu'à ce que le demandeur réponde
Jo King
1

C (clang) , 73 octets

o,j,y;f(x){for(o=j=0;printf("%d ",o),x;o+=y+!y,y+=y+!y)j=!j?y=0,--x:--j;}

Essayez-le en ligne!

for(o=j=0;printf("%d ",o),x;  o+=y+!y, y+=y+!y) 
// adds 1, 1+1=>2 , 2+2=> 4 .... sequence

 j=!j?y=0,--x:--j; 
// uses ternary instead of nested loop to decrement 'x' when 'j' go to 0
AZTECCO
la source
1

k4, 28 24 octets

0,+\"j"$2 xexp,/-1+|,\!:

@ L'approche de Grimy portée à k4

edit: -4 grâce à ngn!

griffonner
la source
1
!:'1+|!:->|,\!:
ngn
vous pouvez supprimer l'espace aprèsxexp
ngn
@ngn, agh |,\!:semble si évident maintenant que je le vois!
grimoire