Tausche Bits mit ihren Nachbarn

26

Aufgabenbeschreibung

Tauschen Sie bei einer Ganzzahl das (2k – 1) -te und das 2k -te niedrigstwertige Bit für alle Ganzzahlen k> 0 aus . Dies ist die Sequenz A057300 im OEIS.

(Es wird angenommen, dass die Zahl "unendlich viele" führende Nullen hat. In der Praxis bedeutet dies einfach, ein einzelnes 0-Bit vor Zahlen ungerader Länge zu setzen.)

Bildbeschreibung hier eingeben

Das ist , also gewinnt der kürzeste Code (in Bytes).

Testfälle

0 -> 0
1 -> 2
9 -> 6
85 -> 170
220 -> 236
1827 -> 2835
47525 -> 30298
Lynn
quelle
5
Können wir annehmen, dass die Zahl als Int für Dinge wie Bitverschiebungen passt?
xnor
1
@xnor: Ich denke das ist der Standard / Community Konsens (sonst wären Antworten in C etc. immer falsch)? So sicher! :)
Lynn
@Lynn: C muss unsigned char array_of_bytes[1024]wie erwartet funktionieren (dh ein Bitfeld mit 1024 * CHAR_BITEinträgen sein). Ich würde mir vorstellen, dass die meisten Antworten, die Eingaben beliebiger Länge unterstützen, CHAR_BITgerade sind, da das Verschieben von Bits zwischen Bytes umständlich ist. Sie können also durchaus kverlangen, dass bis zu einer konstanten Größe wie 256 oder etwas, das für AES angemessen ist, unterstützt wird, und Sprachen ohne 256-Bit-Integer-Typen müssten Schleifen verwenden. Das könnte SIMD-Vektoren für eine x86-asm-Antwort in Betracht ziehen: P
Peter Cordes
2
Ich tausche @Geobits mit Minibits
Optimizer

Antworten:

9

Jelly , 10 9 7 Bytes

b4d2UFḄ

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

b4d2UFḄ  Main link. Argument: n (integer)

b4       Convert n to base 4.
  d2     Divmod each quaternary digit x by 2, yielding [x : 2, x % 2].
    U    Upend; reverse each pair, yielding [x % 2, x : 2].
     F   Flatten the 2D list of binary digits.
      Ḅ  Convert from binary to integer.
Dennis
quelle
20

Python 2, 26 Bytes

lambda n:2*n-3*(4**n/3&n/2)

Bit-Tricks!

Sprich nhat Form ...ghfedcbain binär. Dann können wir es in zwei Teile aufteilen

n   = o + 2*e
n   = ...hgfedcba
o   = ...0g0e0c0a
2*e = ...h0f0d0b0

Dann kann das bitvermittelte Ergebnis sausgedrückt werden als s=2*o+e.

s   = 2*o + e
s   = ...ghefcdab
2*o = ...g0e0c0a0
e   = ...0h0f0d0b

Wir wollen lieber nur eines von eund berechnen o, also drücken wir aus o=n-2*eund ersetzen

s=2*(n-2*e)+e = 2*n-3*e

So, jetzt bleibt es ein Bezug auf auszudrücken n. Die Zahl M=4**n/3hat eine ...10101010101binäre Form , die als Maske für die ungeraden Ziffern dient. Der Exponent nsorgt dafür, dass Mdas lang genug ist. Das bitweise Nehmen andvon n/2und dieser Wert ergibt ewie gewünscht.

n/2     = ...hgfedcb
M       = ...1010101
n/2 & M = ...h0f0d0b = e

Wir können stattdessen ein Begriffen ausdrücken o e=(n-o)/2, was gibt s=(n+o*3)/2, was dank einer Optimierung von xsot ein Byte spart.

lambda n:n+(n&4**n/3)*3>>1
xnor
quelle
Tolle Erklärung und netter Trick, die Maske nur einmal durch Subtrahieren von zu verwenden n. Ich bevorzuge jedoch die entgegengesetzte "ungerade" oder "gerade" Bitbenennungskonvention. Das LSB ist Bit 0, das gerade ist (obwohl es das erste Bit ist). Bei der SIMD-Programmierung, bei der Shuffles häufig Elemente mit einem Index auswählen, werden die Indizes von 0 an gezählt. Daher ist es normal, das niedrige Element als gerade Elemente zu betrachten. zB[ 3 2 1 0 ]
Peter Cordes
Ich habe eine C-Antwort mit Ihrem Ausdruck hinzugefügt. Alle Gutschriften für die Byte-Einsparungen im Vergleich zur C-Antwort von Digital Trauma sind darauf zurückzuführen.
Peter Cordes
2
26:lambda n:n+(n&4**n/3)*3>>1
xsot
@PeterCordes Ihr C-Code funktioniert für mich mit gcc 4.8.3 und Standardeinstellungen. f(x){return x+((x&~0U/3)*3)>>1;}Gibt 1 für Eingabe 2 zurück .
Dennis
@ Tennis: Ja, arbeitet für mich in C, mein schlechtes. Ich habe den Ausdruck in calc(aka apcalc) getestet, nicht in C. Ich dachte, ich wäre in Ordnung, da ich keine Kürzung auf 32-Bit oder das Zweierkomplement benötigte. Ich dachte nicht, dass der Ausdruck richtig aussah, also war ich bereit, meine falschen Tests zu glauben. Trotzdem brauche ich eine bessere REPL für die Entwicklung von Bithacks. Irgendwelche Vorschläge? (Idealerweise Linux-Befehlszeile, wie bc -loder calc, aber tatsächlich verfügbar machen int32_t/ uint32_toder etwas, nicht erweiterte Präzision.)
Peter Cordes
10

C-Funktion, 38

Bit-Twiddling:

f(x){return(x&~0U/3*2)/2+(x&~0U/3)*2;}

Ideone.


Oder zum Spaß:

C rekursive Funktion, 43

Gemäß der OEIS Formel ,a(4n+k) = 4a(n) + a(k), 0 <= k <= 3

f(x){return x>3?4*f(x/4)+f(x%4):x%3?3-x:x;}

oder

f(x){return x>3?4*f(x/4)+f(x%4):x%2*2+x/2;}

Ideone.

Digitales Trauma
quelle
1
xnors clevere Transformation des Ausdrucks reduziert dies auf 32 Bytes in C. Ich habe es als separate Antwort gepostet, da es ein signifikant anderer Ansatz ist.
Peter Cordes
8

CJam, 16 14 13 Bytes

ri4b4e!2=f=4b

Teste es hier.

Erläuterung

ri  e# Read input and convert to integer.
4b  e# Get base-4 digits.
4e! e# Push all permutations of [0 1 2 3].
2=  e# Select the third one which happens to be [0 2 1 3].
f=  e# For each base-4 digit select the value at that position in the previous
    e# list, which swaps 1s and 2s.
4b  e# Convert back from base 4.
Martin Ender
quelle
Dieser Trick mit den Permutationen ist sehr gut!
Luis Mendo
7

Pyth, 9 Bytes

iXjQ4S2)4

Probieren Sie es im Pyth-Compiler aus .

Wie es funktioniert

  jQ4      Convert the input (Q) to base 4.
 X   S2)   Translate [1, 2] to [2, 1].
i       4  COnvert from base 4 to integer.
Dennis
quelle
5

JavaScript (ES6), 32-30 Bytes

(n,m=0x55555555)=>n*2&~m|n/2&m

Funktioniert aufgrund der Einschränkungen der JavaScript-Ganzzahlen nur bis 1073741823. 38 36 Bytes funktioniert bis zu 4294967295:

(n,m=0x55555555)=>(n*2&~m|n/2&m)>>>0

Bearbeiten: 2 Bytes dank @ user81655 gespeichert.

51 Bytes funktioniert bis zu 4503599627370495:

n=>parseInt(n.toString(4).replace(/1|2/g,n=>3-n),4)
Neil
quelle
Könnte n<<1sein n*2?
User81655
@ user81655 Und das kann ich auch gebrauchen n/2! Ich weiß nicht, warum ich vorher nicht daran gedacht habe.
Neil
Ich habe noch nie gesehen >>>... was ist das?
Titus
@Titus Es ist wie, >>>aber es macht eine vorzeichenlose Verschiebung. >>>0Grundsätzlich wird in eine 32-Bit-Ganzzahl ohne Vorzeichen konvertiert.
Neil
5

x86 asm-Funktion: 14 Byte Maschinencode

uint64_t version: 24 bytes

x86-64-SysV-Aufrufkonvention ( xin edi), aber dieser Computercode funktioniert auch im 32-Bit-Modus. (Wobei der leaWille als dekodiert lea eax, [edi + eax*2], was identische Ergebnisse ergibt ).

0000000000000040 <onemask_even>:
  40:   89 f8                   mov    eax,edi
  42:   25 55 55 55 55          and    eax,0x55555555
  47:   29 c7                   sub    edi,eax
  49:   d1 ef                   shr    edi,1
  4b:   8d 04 47                lea    eax,[rdi+rax*2]
  4e:   c3                      ret    
4f: <end>

0x4f - 0x40 = 14 Bytes

Dies ist die Compiler-Ausgabe , wenn die einmalige Masken-Idee von xnor umgekehrt verwendet wird. (Und entgegengesetzte Terminologie: Das niedrige Bit ist Bit 0, das gerade und nicht ungerade ist.)

unsigned onemask_even(unsigned x) {
  unsigned emask = ~0U/3;
  unsigned e = (x & emask);
  return e*2 + ((x - e) >> 1);
}

Ich habe keine Verbesserungen gegenüber dem Compiler gefunden. Ich hätte es vielleicht als mov eax, 0x555.../ geschrieben and eax, edi, aber das ist die gleiche Länge.


Dieselbe Funktion für 64-Bit-Ganzzahlen benötigt 24 Byte (siehe Godbolt-Link). Ich sehe keinen Weg, der kürzer als 10 Byte ist movabs rax, 0x55..., um die Maske in einem Register zu erzeugen. (Die divAnweisung von x86 ist klobig, daher hilft eine Division der Einsen durch drei ohne Vorzeichen nicht.)

Ich habe mir eine Schleife ausgedacht, um die Maske in Rax zu generieren, aber es sind 10 Bytes (genau die gleiche Länge wie die mov imm64).

# since 0x55 has its low bit set, shifting it out the top of RAX will set CF
0000000000000000 <swap_bitpairs64>:
   0:   31 c0                   xor    eax,eax      ; old garbage in rax could end the loop early
0000000000000002 <swap_bitpairs64.loop>:
   2:   48 c1 e0 08             shl    rax,0x8
   6:   b0 55                   mov    al,0x55      ; set the low byte
   8:   73 f8                   jnc    2 <swap_bitpairs64.loop>  ; loop until CF is set
000000000000000a <swap_bitpairs64.rest_of_function_as_normal>:
 # 10 bytes, same as   mov  rax, 0x5555555555555555
 # rax = 0x5555...
   a:   48 21 f8                and    rax,rdi
   ...

Wenn wir wüssten, dass keines der vorhandenen Bytes raxsein niedriges Bit gesetzt hat, könnten wir das überspringen xor, und dies wäre 8 Bytes lang.

Eine frühere Version dieser Antwort hatte eine 10-Byte-Schleife mit dem loopBefehl insn, aber die Laufzeit der 0xFFFFFFFFFFFFFF08Iterationen war im schlimmsten Fall , da ich nur festgelegt habe cl.

Peter Cordes
quelle
5

Oasis , 17 Bytes (nicht konkurrierend)

n4÷axxn4÷xxe+3120

Probieren Sie es online!

Oasis ist eine Sprache von Adnan, die auf Sequenzen spezialisiert ist.

Gegenwärtig kann diese Sprache eine Rekursion und eine geschlossene Form ausführen.

Wir verwenden diese Formel: a(4n+k) = 4a(n) + a(k), 0 <= k <= 3

Den Basisfall zu spezifizieren ist einfach: das bedeutet 3120am Ende einfach das a(0)=0, a(1)=2, a(2)=1, a(3)=3.

n4÷axxn4÷xxe+3120
                0  a(0) = 0
               2   a(1) = 2
              1    a(2) = 1
             3     a(3) = 3

n                  push n (input)
 4÷                integer-divide by 4
   a               a(n/4)
    xx             double twice; multiply by 4
                   now we have 4a(n/4)
      n            push n (input)
       4÷xx        integer-divide by 4 and then multiply by 4
                   since there is no modulo currently, n%4
                   is built as n-(n/4*4)
           e       we should have done a(n-(n/4*4)), but this
                   is a shortcut for a(n-x) where x is the top
                   of stack. Therefore, we now have a(n-n/4*4)
                   which is a(n%4).
            +      add.
Undichte Nonne
quelle
4

MATL , 10 Bytes

BP2eP1ePXB

Probieren Sie es online!

Geänderte Version zur Generierung der ersten Terme der Sequenz ( OEIS A057300 ).

Erläuterung

B     % Take input implicitly. Convert to binary array
P     % Flip
2e    % Convert to two-row 2D array, padding with a trailing zero if needed. 
      % Because of the previous flip, this really corresponds to a leading zero
P     % Flip each column. This corresponds to swapping the bits
1e    % Reshape into a row
P     % Flip, to undo the initial flipping
XB    % Convert from binary array to number. Display implicitly
Luis Mendo
quelle
3

zsh, 28 Bytes

<<<$[`tr 12 21<<<$[[#4]$1]`]

Nimmt Eingaben als Befehlszeilenargument und gibt sie auf STDOUT aus.

Es ist nicht Bash-kompatibel, da es die zsh-spezifische Basiskonvertierungssyntax verwendet.

                       $1     input (first command line argument)
                 $[      ]    arithmetic expansion
                   [#4]       output in base 4
              <<<             pass the result of this to...
      tr                      the `tr' command
         12 21                and replace 1s with 2s, 2s with 1s
     `                    `   evaluate the result...
   $[                      ]  in another arithmetic expansion, to convert back
                                to base 10
<<<                           output the result on STDOUT
Türknauf
quelle
3

Netzhaut, 70 Bytes

. +
$ *
+ `(1 +) \ 1
1x $
x1
1
^
x
r` (.) (.)
$ 2 $ 1
1
x @
+ `@ x
x @@
x * (@ *)
$ .1
0 $

Testsuite. (Leicht verändert.)

Nur zum Spaß: 7 Bytes

T`12`21

Nimmt Base-4 als Eingabe und Ausgänge als Base-4.

Probieren Sie es online!

Undichte Nonne
quelle
4
Ich bin widersprüchlich. Ich möchte die untere Hälfte Ihrer Antwort positiv bewerten, aber die obere Hälfte negativ bewerten.
Dennis
1
@Dennis Jetzt habe ich die Bits getauscht.
Undichte Nonne
3

05AB1E, 8 Bytes

4B12‡4ö

Vielen Dank an @Adnan für -5 Bytes!

Verwendet die CP-1252-Codierung.

Probieren Sie es online!

Erläuterung:

4B       - Take input and convert to base 4.
  12Â    - Push 12 bifurcated.
     ‡   - Transliterate [1, 2] to [2, 1].
      4ö - Convert to base 10.
George Gibson
quelle
2
Schön, aber Sie können 1 2‚2 1‚mit 12Âfür 8 Bytes ersetzen .
Adnan
Gute Antwort! Hier eine 8-Byte-Alternative:4в2‰íJJC
Kevin Cruijssen
3

C 32 30 29 Bytes

f(x){return(x&~0U/3)*3+x>>1;}                // 30 bit version, see below

// less golfed:
f(x){return ((x & 0x55555555)*3 + x) >>1;}   //  >> is lower precedence than +

Algorithmus kopiert aus xsots Kommentar zur Python-Antwort von xnor . Anstatt beide Wege zu maskieren, maskieren Sie einen Weg und kombinieren Sie.

Dies kompiliert auf dieselbe Weise wie die letzte von mir getestete Version und funktioniert (für x bis 0x3FFFFFFFund für x darüber, solange Bit 30 nicht gesetzt ist, siehe unten). Im Maschinencode entspricht es der Länge meiner vorhandenen asm-Antwort.


Die obige Version löscht immer das hohe Bit des Ergebnisses . Die beste sichere Version ist 32 Bytes:

g(x){return 2*x-3*(x/2U&~0U/3);}   // safe 32bit version, works for all x

Die Python-Version hat dieses Problem nicht, da Python bei Bedarf Integer-Typen mit willkürlicher Genauigkeit verwendet , anstatt auf eine feste Obergrenze zu kürzen.

Peter Cordes
quelle
@ Tennis: Argh, ja, danke. Ich habe diese letzte Änderung nach dem Testen vorgenommen und den Unterschied in der ASM-Ausgabe übersehen. Kein Wunder, dass ich dachte, dass es falsch aussah. Ich hatte vergessen, dass >>das so gering war. Ich spiele nicht oft genug Golf, um mich genau an die Regeln zu erinnern, da Compiler-Warnungen, die in gefährlichen Fällen auf Parens hindeuten, mich in echtem Code retten. : P
Peter Cordes
2
Sie können dieses Leerzeichen löschen, indem Sie die Begriffe im Ausdruck neu anordnen.
Xsot
2

Javascript (ES6), 113 109 Bytes

4 Bytes gespart dank Upgoat

n=>+('0b'+/(..)+$/.exec('0'+n.toString`2`)[0].split``.reduce((p,c)=>p.length-1?[p.join(c)]:[p[0],c],[''])[0],2)

Wie es funktioniert

n=>+('0b'+                              //parse as binary literal
    /(..)+$/.exec('0'+n.toString`2`)[0] //convert to binary string with an even number of digits
        .split``                        //convert to array
        .reduce((p,c)=>p.length-1?[p.join(c)]:[p[0],c],[''])
                                        //swap all numbers
)
Nur ASCII
quelle
Verwenden Sie +('0b"+binary_string_here)anstelle von "parseInt (..., 2)
Downgoat
1

J, 20 Bytes

4#.0 2 1 3{~4#.^:_1]

Verwendung

>> f =: 4#.0 2 1 3{~4#.^:_1]
>> f 85
<< 170

Wo >>ist STDIN und <<ist STDOUT.

Ungolfed

to_base   =: 4 #.^:_1 ]
transpose =: 0 2 1 3 {~ to_base
from_base =: 4 #. transpose

Drei Gabeln.

Randnotiz

Im offiziellen Interpreter ^:_1kann durch inv1 Byte erspart werden.

Keiner der Online-Dolmetscher setzt dies jedoch um.

Undichte Nonne
quelle
1

C #, 44 Bytes

Basierend auf der C-Implementierung

int f(int n)=>n>3?4*f(n/4)+f(n%4):n%2*2+n/2;

Probieren Sie es hier aus: C # Pad

Cheesebaron
quelle
1

INTERCAL , 60 Bytes

DOWRITEIN.1PLEASE.1<-!1~#21845'$.1~#43690DOREADOUT.1DOGIVEUP

Probieren Sie es online!

Funktioniert für 16-Bit-Ganzzahlen, wobei E / A im natürlichsten Format für INTERCAL ausgeführt wird: Die Eingabe ist eine Reihe von Dezimalstellen, die in einer von mehreren natürlichen oder konstruierten Sprachen geschrieben sind, und die Ausgabe erfolgt in "geschlachteten römischen Ziffern".

Dies ist eine der seltenen Herausforderungen, bei denen die binären Operatoren von INTERCAL überhaupt intuitiv verwendet werden können, da es um das Neupositionieren von Bits geht. Select ( ~) nimmt die Bits aus seinem ersten Argument, die den Einsen in seinem zweiten Argument entsprechen, und füllt sie rechts mit Nullen auf, und mingle ( $) verschachtelt die Bits aus seinen Argumenten, sodass die Bits aus dem ersten Argument signifikanter sind. Die einfache Lösung besteht also darin, die niederwertigen alternierenden Bits ( .1~#21845) und die höherwertigen alternierenden Bits ( ) auszuwählen..1~#43690), und verschachteln Sie sie in umgekehrter Reihenfolge. Zum Glück für die Byteanzahl haben die INTERCAL-Operatoren zwar keine definierte Priorität (da die Sprache keine Präzedenzfälle haben soll), es stellt sich jedoch heraus, dass C-INTERCAL auf TIO für diesen bestimmten Ausdruck keine große Gruppierung erfordert und nur ein Byte kostet '.kann abgekürzt werden !.

Mit Unterstützung für 32-Bit-Ganzzahlen:

INTERCAL , 67 Bytes

DOWRITEIN:1PLEASE:1<-':1~#0$#65535'$:1~#65535$#0DOREADOUT:1DOGIVEUP

Probieren Sie es online!

INTERCAL erlaubt keine 32-Bit-Literale, was das Lesen tatsächlich ein wenig erleichtert , da die magischen Konstanten für die Auswahl alternierender Bits konstruiert werden müssen, indem zwei 16-Bit-Literale miteinander gemischt werden, wobei einer alle Nullen und der andere alle Nullen enthält alle. (Selbst wenn es 32-Bit-Literale gäbe, wäre diese immer noch kürzer. Sie #0$#65535ist zwei Bytes entfernt #1431655765, und das Gleiche gilt für die andere.) Dadurch wird der gesamte Prozess für INTERCAL unnatürlich gut kommuniziert.

Ein alternativer Ansatz mit umständlicher Verwendung der Operandenüberladung :

INTERCAL , 71 Bytes

DO:1<-:1/.2$.3PLEASEWRITEIN:2DO:1<-:2PLEASE:2<-.3$.2DOREADOUT:2DOGIVEUP

Probieren Sie es online!

Dies beseitigt die Auswahl insgesamt, indem deklariert wird, dass :1mit .2gemischt wird .3, :1auf den Eingang gesetzt wird und dann mit gemischt .3ausgegeben wird .2. Since :1wurde überladen als .2$.3, DO :1 <- :2weist Werte zu .2und .3so zu, dass :1der Wert von erfasst wird :2, was dazu führt, dass die höherwertigen .2Wechselbits von :2und .3die niederwertigen Wechselbits enthalten sind. Dies wäre die kürzere der beiden 32-Bit-Lösungen um vier Bytes, wenn PLEASE WRITE IN :1sie durch PLEASE WRITE IN :2 DO :1 <- :2überlastete ersetzt werden könnten:1 , aberCALCULATINGerweist sich als notwendig für die Verwendung von Überladung. Ich habe auch das Gefühl, dass es einen kürzeren Weg gibt, das Überladen selbst durchzuführen, als das Programm zu starten DO:1<-:1/.2$.3, aber da dies INTERCAL ist, habe ich auch das Gefühl, dass es keinen geben kann.

Nicht verwandte Zeichenfolge
quelle
0

Mathematica, 44 Bytes

Fold[3#+##&,#~IntegerDigits~4/.{1->2,2->1}]&

Gleicher Ansatz wie meine CJam-Antwort: In Base-4 konvertieren, 1s und 2s tauschen, zurück konvertieren. Es wird auch der alephalpha-Trick verwendet, um ihn FromDigitsdurch eine FoldOperation zum Speichern eines Bytes zu ersetzen .

Martin Ender
quelle
0

Eigentlich 16 Bytes

4@¡"21""12"(t4@¿

Probieren Sie es online!

Erläuterung:

4@¡"21""12"(t4@¿
4@¡               base 4 representation of n
   "21""12"(t     translate (swap 1s and 2s)
             4@¿  base 4 to decimal
Mego
quelle
0

J, 22 Bytes

([:,_2|.\,&0)&.(|.@#:)

Alternativer Ansatz basierend auf Array-Manipulation anstelle des Basis-4-Tricks.

Verwendung

   f =: ([:,_2|.\,&0)&.(|.@#:)
   (,.f"0) 0 1 9 85 220 1827 47525
    0     0
    1     2
    9     6
   85   170
  220   236
 1827  2835
47525 30298

Erläuterung

([:,_2|.\,&0)&.(|.@#:)  Input: n
                   #:   Get the value as a list of base 2 digits
                |.@     Reverse it
(           )&.         Apply to the list of base 2 digits
         ,&0            Append a zero to the end of the list
    _2  \               Split the list into nonoverlapping sublists of size 2
      |.                Reverse each sublist
 [:,                    Flatten the list of sublists into a list
             &.(    )   Apply the inverse of (reversed base 2 digits)
                        to convert back to a number and return it
Meilen
quelle
0

REXX, 88 Bytes

n=x2b(d2x(arg(1)))
o=0
do while n>''
  parse var n a+1 b+1 n
  o=o||b||a
  end
say x2d(b2x(o))
idrougge
quelle