Löschen des höchstwertigen Bits aus einer Ganzzahl

29

Eingang

Die Eingabe ist eine einzelne positive Ganzzahl n

Ausgabe

Der Ausgang ist nmit dem höchstwertigen Bit auf gesetzt 0.

Testfälle

1 -> 0
2 -> 0
10 -> 2
16 -> 0
100 -> 36
267 -> 11
350 -> 94
500 -> 244

Zum Beispiel: 350in binär ist 101011110. Durch Setzen des höchstwertigen Bits (dh des am weitesten links liegenden 1Bits) wird die Ausgabe 0in ein Bit umgewandelt 001011110, das der dezimalen Ganzzahl 94entspricht. Dies ist OEIS A053645 .

code-golf sequence binary Marcus Andrews
quelle

19

Das Löschen des höchstwertigen Bits von 10ergibt offensichtlich 0: D

Clabacchio

@clabacchio Ich .. es ... ähm ... was? (Schön)

Baldrickk

12

Mir scheint, dass die Nullen genauso wichtig sind wie die Einsen. Wenn Sie "das höchstwertige Bit" sagen, meinen Sie "das höchstwertige Bit, das auf eins gesetzt ist".

Michael Kay

Antworten:

12

C (gcc) , 49 44 40 39 Bytes

i;f(n){for(i=1;n/i;i*=2);return n^i/2;}

Probieren Sie es online!

Cleblanc
quelle

1

Sie können ersetzen i<=nmit n/ifür -1 Byte. Dies ist nicht mein Golf, jemand anderes hat versucht, es in Ihrem Post zu bearbeiten, aber ich habe es zurückgesetzt, weil Änderungen für Golfposts gemäß unseren Community-Regeln nicht akzeptiert werden.

HyperNeutrino

1

@HyperNeutrino Ich habe die Bearbeitung gerade gesehen und genehmigt. War mir dieser Regel nicht bewusst, aber es ist ein schöner Golftipp!

Cleblanc

Ah okay. Ja, normalerweise sollten Leute Kommentare zu Golftipps posten und OP sollte die Änderungen vornehmen, aber wenn Sie das akzeptieren, ist es nicht wirklich so ein Problem. :)

HyperNeutrino

10

Python 2 , 27 Bytes

lambda n:n^2**len(bin(n))/8

Probieren Sie es online!

26 Bytes

Leider funktioniert dies nicht für 1:

lambda n:int(bin(n)[3:],2)

Probieren Sie es online!

FlipTack
quelle

9

05AB1E , 5 Bytes

.²óo-

Probieren Sie es online!

Das Entfernen des höchstwertigen Bits von einer ganzen Zahl N entspricht dem Ermitteln des Abstands von N zur höchsten ganzzahligen Potenz von 2, die niedriger als N ist .

Daher habe ich die Formel N - 2 ^{floor (log ₂ N) verwendet} :

.²- Logarithmus mit Basis 2 .
ó - Floor auf eine ganze Zahl.
o- 2 erhöht auf die Potenz des obigen Ergebnisses.
- - Unterschied.

Mr. Xcoder
quelle

1

b¦Cfunktioniert auch ... nicht wahr? In Binär konvertieren, MSB ist immer auf Index 1, MSB entfernen, zurückkonvertieren.

Magic Octopus Urn

2

@MagicOctopusUrn Nein, das ist falsch, scheitert 1!

Mr. Xcoder

8

Gelee , 3 Bytes

BḊḄ

Probieren Sie es online!

Erläuterung

BḊḄ  Main Link
B    Convert to binary
 Ḋ   Dequeue; remove the first element
  Ḅ  Convert from binary

HyperNeutrino
quelle

2

Sind nicht Ḅund ḊZwei-Byte - Codepoints? Dies würde die Gesamtgröße auf 5 Bytes ändern.

Bartek Banachewicz

3

@BartekBanachewicz Jelly verwendet eine eigene Codepage , wobei diese Zeichen nur 1 Byte lang sind.

Steenbergh

1

Vielen Dank für Ihre Fragen und Antworten, das hat mich schon lange beschäftigt!

Ukko

8

C (gcc) - 59 Bytes

main(i){scanf("%d",&i);return i&~(1<<31-__builtin_clz(i));}

Diese gcc-Antwort verwendet nur ganzzahlige bitweise und arithmetische Operationen. Keine Logarithmen hier! Es kann Probleme mit der Eingabe von 0 geben und ist nicht portierbar.

Es ist meine erste Antwort auf dieser Website, daher würde ich mich über Feedback und Verbesserungen freuen. Ich hatte wirklich Spaß daran, bitweise Ausdrücke zu lernen.

Charles-Diplom
quelle

1

Willkommen bei PPCG und tolle erste Antwort! Wir

wünschen

Sie brauchen kein vollständiges Programm mit main, eine Funktion ist eine gültige Einreichung . Wenn Sie dies in eine Funktion umwandeln und die Eingabe als Argument für diese Funktion verwenden, werden 18 Byte gespart .

Steadybox

1

Sie könnten es sogar als Makro schreiben, um zwei weitere Bytes zu sparen .

Steadybox

7

MATL , 8 6 Bytes

B0T(XB

Probieren Sie es online!

Zwei Bytes gespart dank Cinaski. Der Wechsel zur Zuweisungsindizierung anstelle der Referenzindizierung war 2 Byte kürzer :)

Erläuterung:

          % Grab input implicitly: 267
B         % Convert to binary: [1 0 0 0 0 1 0 1 1]
 0T(      % Set the first value to 0: [0 0 0 0 0 1 0 1 1]
    XB    % Convert to decimal: 11

Stewie Griffin
quelle

1

Sie hätten die Referenzindizierung (auch für 6 Bytes) verwenden können, wenn Sie 4Lstattdessen verwendet hätten [2J]. Ein weiterer Spaß 6 Bytes: tZlcW-(funktioniert nur in MATLAB, nicht in TIO / Octave)

Sanchises

6

Java (OpenJDK 8) , 23 Byte

n->n^n.highestOneBit(n)

Probieren Sie es online!

Entschuldigung, eingebaut: - /

Olivier Grégoire
quelle

Java mit einem Build-in, das einige andere beliebte Sprachen wie .NET und Python nicht hat ?! o.Ô +1 dazu. Wollte etwas länger posten ohne Einbauten .. Deine ist 15 Bytes kürzer. XD

Kevin Cruijssen

@ KevinCruijssen So etwas n->n^1<<(int)Math.log2(n)wird funktionieren und ist wahrscheinlich kürzer als 38 Bytes. Es war meine zweite (noch nicht getestete) Idee, wenn die nicht richtig highestOneBitfunktionierte. Aus Neugier, was war Ihre Lösung

Olivier Grégoire

Meins war, n->n^1<<(int)(Math.log(n)/Math.log(2))weil Math.log2es in Java nicht gibt. Nur P; Math.log, Math.log10und Math.loglpverfügbar sind.

Kevin Cruijssen

2

Ich würde das selbe posten, nur minus statt xor. Erinnerte sich an die Methode von diesem

JollyJoker

1

@ KevinCruijssen Ups, Math.log2gibt es in der Tat nicht ... Mein schlechtes. Sehen? Eine nette Methode ( highestOneBit) existiert, aber keine andere ( Math.log2). Java ist komisch ;-)

Olivier Grégoire

6

Schale , 3 Bytes

ḋtḋ

Probieren Sie es online!

Erläuterung:

    -- implicit input, e.g. 350
  ḋ -- convert number to list of binary digits (TNum -> [TNum]): [1,0,1,0,1,1,1,1,0]
 t  -- remove first element: [0,1,0,1,1,1,1,0]
ḋ   -- convert list of binary digits to number ([TNum] -> TNum): 94

Laikoni
quelle

Ähnlich wie bei der Jelly-Lösung

sieht es so aus, als wären

1

@BartekBanachewicz ähnlich Jelly verwendet Husk seine eigene Codepage, so dass dies ist tatsächlich 3 Bytes: P

HyperNeutrino

@BartekBanachewicz Hier finden Sie die Codepage: github.com/barbuz/Husk/wiki/Codepage

Laikoni

5

Ohm v2 , 3 Bytes

b(ó

Probieren Sie es online!

Cinaski
quelle

5

Python 2 , 27 Bytes

lambda n:n-2**len(bin(n))/8

Probieren Sie es online!

Erläuterung

lambda n:n-2**len(bin(n))/8  # Lambda Function: takes `n` as an argument
lambda n:                    # Declaration of Lambda Function
              len(bin(n))    # Number of bits + 2
           2**               # 2 ** this ^
                         /8  # Divide by 8 because of the extra characters in the binary representation
         n-                  # Subtract this from the original

HyperNeutrino
quelle

... Gerade als ich die bitweise Mathematik ausarbeitete. : P

totalhuman

@totallyhuman heh sorry, aber schlagen Sie es: P

HyperNeutrino

2**len(bin(n))/8kann auch geschrieben 1<<len(bin(n))-3werden und funktioniert dann in 2 und 3 (keine Bytes gespeichert / hinzugefügt).

Mego

@Mego Cool, danke für den Zusatz!

HyperNeutrino

5

Python 3 , 30 Bytes

-8 bytes dank caird coinheringaahing. ^{Ich habe das aus dem Gedächtnis getippt. :O}

lambda n:int('0'+bin(n)[3:],2)

Probieren Sie es online!

total menschlich
quelle

Warum nicht lambda n:int(bin(n)[3:],2)?

Caird Coinheringaahing

Nun, a) das wäre ein Fehler bei 1 , b) ich bin dumm genug, nicht daran zu denken. Aber ich habe es mit einer kleinen Änderung behoben. Vielen Dank!

Totalhuman

Ich habe den Code so bearbeitet, dass er funktioniert (und 4 Bytes spart)

Caird Coinheringaahing

Das sind noch Fehler am 1 .

totallyhuman

@cairdcoinheringaahing Das war meine ursprüngliche Antwort , aber dann bemerkte ich, dass es am 1. fehlerhaft war. Die Problemumgehung endet länger als eine einfache XOR-Methode

FlipTack

4

Mathematica, 37 Bytes

Rest[#~IntegerDigits~2]~FromDigits~2&

Probieren Sie es online!

J42161217
quelle

4

JavaScript, 22 bis 20 Byte

2 Bytes dank ovs gespart

a=>a^1<<Math.log2(a)

Probieren Sie es online!

Ein weiterer Ansatz, 32 Bytes

a=>'0b'+a.toString`2`.slice`1`^0

Probieren Sie es online!

quelle

warum würdest du es tun, .slice`1`^0wenn .slice(1)^0es genauso gut funktionieren würde, haha

ETHproductions 15.11.17

@ETHproductions. Dieser sieht besser aus :)

4

J, 6 Bytes

}.&.#:

Ziemlich einfach.

Erläuterung

}.&.#:
    #:  convert to list of binary digits
  &.    apply right function, then left, then the inverse of right
}.      behead

cole
quelle

Ich wollte dies posten :(

Cyoce

@Cyoce ich auch ...

Adám

4

APL (Dyalog) , 10 Bytes

Tacit-Präfix-Funktion.

2⊥1↓2∘⊥⍣¯1

Probieren Sie es online!

2∘⊥... decode von der Basis-2 ...
... ⍣¯1 negativer Zeit (dh in encode Basis-2)

1↓ Lass das erste Bit fallen

2⊥ Dekodiere von der Basis 2

Adam
quelle

4

Ruby, 26 Bytes

-7 Bytes dank Ventero. -2 Bytes dank historicrat.

->n{/./=~'%b'%n;$'.to_i 2}

Anzeigename
quelle

Sie können ein paar Bytes sparen, indem Sie einfach das erste Zeichen überspringen und redundante Klammern ->n{n.to_s(2)[1..-1].to_i 2}

löschen

->n{/./=~'%b'%n;$'.to_i 2}

Histokrat

4

C (gcc), 38 Bytes

Eingebauter GCC verwendet.

f(c){return c^1<<31-__builtin_clz(c);}

Colera Su
quelle

Durch Ersetzen 31-durch ~sollten zwei Bytes gespart werden.

@ThePirateBay es hängt von der Hardware ab, ob die Verschiebung maskiert ist. Auf meinem Computer wird 0 ausgegeben.

Colera So

4

ARM-Assembly, 46 43 Byte

(Sie können das Zielregister beim Hinzufügen weglassen, wenn es mit der Quelle identisch ist.)

clz x1,x0
add x1,1
lsl x0,x1
lsr x0,x1
ret

Michael Dorgan
quelle

Welche Variante der ARM-Assemblysyntax ist dies? Mein GNU-Assembler versteht shr/ shl/ nicht retund möchte stattdessen etwas wie lsr/ lsl/ bx lr.

Ruslan

Vermutlich mischen Syntax über mehrere Versionen (ret ist von aarch64), obwohl ich dachte, dass der Assembler diese für Sie pseudo op würde. In diesem Fall ist die Verwendung des älteren und direkten lsl / lsr wahrscheinlich richtig.

Michael Dorgan

Lustige Sache, ich kann es in 1 weniger Betrieb tun, aber ich die Byte-Größe um 2 erhöht. Ah Code Golf.

Michael Dorgan

3

Pyth, 5 Bytes

a^2sl

Erläuterung:

    l   Log base 2 of input.
   s    Cast ^ to integer (this is the position of the most significant bit.)
 ^2     Raise 2 to ^ (get the value of said bit)
a       Subtract ^ from input

Steven H.
quelle

3

Alice , 8 Bytes

./-l
o@i

Probieren Sie es online!

Erläuterung

.   Duplicate an implicit zero at the bottom of the stack. Does nothing.
/   Switch to Ordinal mode, move SE.
i   Read all input as a string.
l   Convert to lower case (does nothing, because the input doesn't contain letters).
i   Try reading all input again, pushes an empty string.
/   Switch to Cardinal mode, move W.
.   Duplicate. Since we're in Cardinal mode, this tries to duplicate an integer.
    To get an integer, the empty string is discarded implicitly and the input is 
    converted to the integer value it represents. Therefore, at the end of this,
    we get two copies of the integer value that was input.
l   Clear lower bits. This sets all bits except the MSB to zero.
-   Subtract. By subtracting the MSB from the input, we set it to zero. We could
    also use XOR here.
/   Switch to Ordinal, move NW (and immediately reflect to SW).
o   Implicitly convert the result to a string and print it.
/   Switch to Ordinal, move S.
@   Terminate the program.

Martin Ender
quelle

3

Japt , 6 Bytes

^2p¢ÊÉ

Probieren Sie es online!

Erläuterung

^2p¢ÊÉ
   ¢     Get binary form of input
    Ê    Get length of that
     É   Subtract 1
 2p      Raise 2 to the power of that
^        XOR with the input

Wenn die Eingabe `1`fehlschlagen kann: 4 Bytes

¢Ån2

Probieren Sie es online!

Erläuterung : Ruft die Eingabe binary ( ¢) ab, schneidet das erste Zeichen ( Å) ab und parst sie als binär zurück zu einer Zahl ( n2).

Justin Mariner
quelle

3

Oktave , 20 Bytes

@(x)x-2^fix(log2(x))

Probieren Sie es online!

Luis Mendo
quelle

3

APL (Dyalog Unicode) , 9 Bytes

⊢-2*∘⌊2⍟⊢

Probieren Sie es online!

-1 Byte danke an Adam

HyperNeutrino
quelle

Ganz richtig, obwohl ich mit TIO ein Template für mich erstellt hätte. Wie auch immer, ⊢-2*∘⌊2⍟⊢spart ein Byte.

Adám

Ich war traurig, dass APL nicht vertreten war, und es war, fast in der Schriftrolle verloren! Ich vermisse APL.

cmm

@cmm APL ist am Leben und gut. Sie können sich gerne im Stack Exchange APL-Chatroom aufhalten .

Adám

3

CJam , 7 Bytes

{2b()b}

Probieren Sie es online!

Erläuterung:

{     }  Block:         267
 2b      Binary:        [1 0 0 0 0 1 0 1 1]
   (     Pop:           [0 0 0 0 1 0 1 1] 1
    )    Increment:     [0 0 0 0 1 0 1 1] 2
     b   Base convert:  11

Verwenden Sie das MSB (das immer 1 ist) erneut, um zu vermeiden, dass es gelöscht werden muss. das Äquivalent ohne diesen Trick wäre {2b1>2b}oder {2b(;2b}.

Esolanging Fruit
quelle

3

Retina , 15 bis 13 Bytes

^(^1|\1\1)*1

Probieren Sie es online!

Ein- und Ausgabe in unary (die Testsuite enthält aus Bequemlichkeitsgründen die Konvertierung von und nach Dezimal).

Erläuterung

Dies ist in unary ziemlich einfach zu tun. Wir wollen nur die größte Potenz von 2 aus der Eingabe löschen. Wir können eine Potenz von 2 mit einigen Vorwärtsreferenzen abgleichen. Es ist tatsächlich einfacher, Werte der Form 2 ⁿ -1 abzugleichen , also werden wir das tun und eine 1 separat abgleichen:

^(^1|\1\1)*1

Die Gruppe 1stimmt entweder 1zu Beginn mit einer einzelnen überein, um die Sache anzukurbeln, oder sie stimmt doppelt mit der letzten Iteration überein. So passt es 1, dann 2, dann4 und so weiter. Da diese addiert werden, haben wir immer eine Potenz von 2, die wir mit der korrigieren1 am Ende .

Aufgrund des nachfolgenden Zeilenvorschubs wird die Übereinstimmung einfach aus der Eingabe entfernt.

Martin Ender
quelle

3

R , 28 Bytes

function(x)x-2^(log2(x)%/%1)

Probieren Sie es online!

Es ist am einfachsten, das höchstwertige Bit über zu berechnen, 2 ^ floor(log2(x))anstatt Basisumwandlungen durchzuführen, die in R ziemlich ausführlich sind

user2390246
quelle

3

PARI / GP, 18 Bytes

n->n-2^logint(n,2)

Alternative Lösung:

n->n-2^exponent(n)

Charles
quelle

Der erste scheint falsche Antworten zu geben. Sollte es sein n->n-2^logint(n,2)? Die zweite Version wird in meiner PARI / GP-Version und in der von tio.run verwendeten Version nicht unterstützt . Ist das eine neue Funktion?

Jeppe Stig Nielsen

@JeppeStigNielsen Hoppla, behoben - das bekomme ich, wenn ich es von meinem Telefon abschicke. Ja, die zweite Funktion ist neu.

Charles

@JeppeStigNielsen Ich habe gerade geprüft, exponentwurde vor 5 Tagen hinzugefügt, verglichen mit dieser Herausforderung, die gestern hinzugefügt wurde. :)

Charles

3

Haskell , 32 29 Bytes

(!1)
x!y|2*y>x=x-y|z<-2*y=x!z

Probieren Sie es online!

-3 Bytes dank @Laikoni

Ältere Lösung, 32 Bytes

f x=last[x-2^i|i<-[0..x],2^i<=x]

Probieren Sie es online!

user28667
quelle

1

Anonyme Funktionen sind erlaubt, so dass Sie die f=in der ersten Variante nicht benötigen . Spart zusätzlich z<-2*y=x!zein Byte: Online ausprobieren!

Laikoni

3

Excel, 20 Bytes

=A1-2^INT(LOG(A1,2))

IanM_Matrix1
quelle

Willkommen auf der Seite! :)

DJMcMayhem

3

Excel, 36 31 Bytes

-5 Bytes dank @ IanM_Matrix1

=BIN2DEC(MID(DEC2BIN(A1),2,99))

Nichts Interessantes.

Wernisch
quelle

Reduzieren Sie die Größe auf 31 Byte, indem Sie REPLACE durch ein MID ersetzen: = BIN2DEC (MID (DEC2BIN (A1), 2,99))

IanM_Matrix1