Usuwanie najbardziej znaczącego bitu z liczby całkowitej

29

Wkład

Dane wejściowe to pojedyncza dodatnia liczba całkowita n

Wydajność

Wyjście ma nnajbardziej znaczący bit ustawiony na 0.

Przypadki testowe

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

Na przykład: 350w pliku binarnym jest 101011110. Ustawienie jego najbardziej znaczącego bitu (tj. Bitu najbardziej z lewej strony 1), aby 0przekształcić go w 001011110ekwiwalent dziesiętnej liczby całkowitej 94, czyli wyjścia. To jest OEIS A053645 .

code-golf sequence binary Marcus Andrews
źródło
19
Usunięcie najważniejszego fragmentu z 10oczywiście daje 0: D
clabacchio
@clabacchio I .. it ... ee ... co? (fajny)
Baldrickk
12
Wydaje mi się, że zera są tak samo znaczące jak jedynki. Kiedy mówisz „najbardziej znaczący bit”, masz na myśli „najbardziej znaczący bit, który jest ustawiony na jeden”.
Michael Kay

Odpowiedzi:

12

C (gcc) , 49 44 40 39 bajtów

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

Wypróbuj online!

cleblanc
źródło
1
Można wymienić i<=nz n/ina -1 bajt. To nie jest mój golf. Ktoś inny próbował go edytować w swoim poście, ale wycofałem go, ponieważ zmiany postów do gry w golfa nie są akceptowane zgodnie z zasadami naszej społeczności.
HyperNeutrino,
1
@HyperNeutrino Właśnie widziałem i zatwierdziłem zmianę. Nie wiedziałem o tej zasadzie, ale to fajna wskazówka golfowa!
cleblanc
Ah, dobrze. Tak, zazwyczaj ludzie powinni publikować komentarze do wskazówek golfowych, a OP powinien wprowadzać zmiany, ale jeśli je zaakceptowałeś, nie jest to tak naprawdę duży problem. :)
HyperNeutrino,
9

05AB1E , 5 bajtów

.²óo-

Wypróbuj online!

Usunięcie najbardziej znaczącego bitu z liczb całkowitych n jest równoważna do znalezienia odległości od N do najwyższej mocy całkowitą od 2 niższej niż N .

Dlatego użyłem wzoru N - 2 piętro (log 2 N) :

  • .²- Logarytm z podstawą 2 .
  • ó - Piętro do liczby całkowitej.
  • o- 2 podniesione do potęgi wyniku powyżej.
  • - - Różnica.
Pan Xcoder
źródło
1
b¦Cdziała również ... prawda? Konwertuj na binarny, MSB jest zawsze pod indeksem 1, usuń MSB, przekonwertuj z powrotem.
Magic Octopus Urn
2
@MagicOctopusUrn Nie, to źle, nie udaje się 1!
Pan Xcoder,
8

Galaretka , 3 bajty

BḊḄ

Wypróbuj online!

Wyjaśnienie

BḊḄ  Main Link
B    Convert to binary
 Ḋ   Dequeue; remove the first element
  Ḅ  Convert from binary
HyperNeutrino
źródło
2
Nie są Ḅi Ḋdwu-bajtowych codepoints? To zmieni ogólny rozmiar na 5 bajtów.
Bartek Banachewicz
3
@BartekBanachewicz Jelly używa własnej strony kodowej , gdzie znaki te mają tylko 1 bajt.
steenbergh
1
Dziękuję, że pytasz i odpowiadasz na to, co martwiło mnie od dawna!
Ukko
8

C (gcc) - 59 bajtów

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

Ta odpowiedź gcc używa tylko liczb całkowitych operacji bitowych i arytmetycznych. Brak logarytmów tutaj! Może mieć problemy z wejściem 0 i jest całkowicie nieprzenośny.

To moja pierwsza odpowiedź na tej stronie, więc chciałbym poznać opinie i ulepszenia. Na pewno dobrze się bawiłem, ucząc się wyrażeń bitowych.

Dyplom Karola
źródło
1
Witamy w PPCG i świetna pierwsza odpowiedź! Mamy nadzieję, że spodoba ci się udział w wielu innych wyzwaniach :-)
ETHproductions
Nie potrzebujesz pełnego programu main, funkcja jest prawidłowym przesłaniem . Zmiana tego na funkcję i przyjęcie danych wejściowych jako argumentu dla tej funkcji pozwala zaoszczędzić 18 bajtów .
Steadybox
1
Możesz nawet napisać to jako makro, aby zaoszczędzić jeszcze dwa bajty .
Steadybox
7

MATL , 8 6 bajtów

B0T(XB

Wypróbuj online!

Zaoszczędził dwa bajty dzięki Cinaski. Przejście na indeksowanie przypisań zamiast indeksowania referencyjnego było o 2 bajty krótsze :)

Wyjaśnienie:

          % 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
źródło
1
Możesz użyć indeksowania referencyjnego (także dla 6 bajtów), jeśli użyłeś 4Lzamiast [2J]. Kolejna zabawa 6 bajtów: tZlcW-(działa tylko w MATLAB, nie w TIO / Octave)
Sanchises
6

Java (OpenJDK 8) , 23 bajty

n->n^n.highestOneBit(n)

Wypróbuj online!

Przepraszamy, wbudowane: - /

Olivier Grégoire
źródło
Java z wbudowaną wersją, której nie mają niektóre inne popularne języki, takie jak .NET i Python ?! o.Ô +1 do tego. Miałem zamiar opublikować coś dłuższego bez wbudowanych elementów. Twój jest o 15 bajtów krótszy. XD
Kevin Cruijssen
@KevinCruijssen Coś podobnego n->n^1<<(int)Math.log2(n)będzie działać i prawdopodobnie będzie miało mniej niż 38 bajtów. To był mój drugi (jeszcze nie przetestowany) pomysł, jeśli ten highestOneBitnie działał odpowiednio. Z ciekawości, jakie było twoje rozwiązanie
Olivier Grégoire,
Mój był, n->n^1<<(int)(Math.log(n)/Math.log(2))ponieważ Math.log2nie istnieje w Javie. ; P Tylko Math.log, Math.log10i Math.loglpsą dostępne.
Kevin Cruijssen
2
Zamierzałem opublikować to samo, tylko minus zamiast xor. Pamiętam metodę z tego
JollyJoker
1
@KevinCruijssen Ups, Math.log2naprawdę nie istnieje ... Mój zły. Widzieć? highestOneBitIstnieje jedna niezła metoda ( ), ale nie ma innej ( Math.log2). Java jest dziwna ;-)
Olivier Grégoire
6

Łuska , 3 bajty

ḋtḋ

Wypróbuj online!

Wyjaśnienie:

    -- 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
źródło
Podobnie jak w rozwiązaniu Jelly, to wydaje się, że to rzeczywiście 5 bajtów, a nie 3.
Bartek Banachewicz
1
@BartekBanachewicz Podobnie jak Jelly, Husk używa własnej strony kodowej, więc w rzeczywistości są to 3 bajty: P
HyperNeutrino,
@BartekBanachewicz Zobacz tutaj stronę kodową: github.com/barbuz/Husk/wiki/Codepage
Laikoni
5

Python 2 , 27 bajtów

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

Wypróbuj online!

Wyjaśnienie

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
źródło
... Właśnie wtedy, gdy pracowałem nad matematyką bitową. : P
totalnie ludzki,
@totallyhuman heh przepraszam, ale cię pokonałem: P
HyperNeutrino
2**len(bin(n))/8można również przeliterować 1<<len(bin(n))-3, a wtedy będzie działać zarówno w 2, jak i 3 (nie zapisano / nie dodano żadnych bajtów).
Mego
@Mego Cool, dzięki za dodanie!
HyperNeutrino,
5

Python 3 , 30 bajtów

-8 bajtów dzięki Cairney Coheringaahing. Wpisałem to z pamięci. : o

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

Wypróbuj online!

całkowicie ludzki
źródło
Dlaczego nie lambda n:int(bin(n)[3:],2)?
caird coinheringaahing
Cóż, a) to by błąd na 1 , b) Jestem na tyle głupi, żeby o tym nie myśleć. Ale naprawiłem to z niewielką zmianą. Dzięki!
całkowicieludzki
Zmodyfikowałem kod, aby działał
To wciąż błędy na 1 .
całkowicieludzki
@cairdcoinheringaahing To była moja pierwotna odpowiedź , ale potem zdałem sobie sprawę, że ją zignorowałem na 1. Obejście kończy się dłużej niż prosta metoda XOR
FlipTack
4

Mathematica, 37 bajtów

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

Wypróbuj online!

J42161217
źródło
4

JavaScript, 22 20 bajtów

Zaoszczędzono 2 bajty dzięki ovs

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

Wypróbuj online!

Inne podejście, 32 bajty

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

Wypróbuj online!


źródło
dlaczego miałbyś zrobić, .slice`1`^0kiedy .slice(1)^0miałby równie dobrze działać, haha
ETHprodukcje
@ETHproductions. Ten wygląda lepiej :)
4

J, 6 bajtów

}.&.#:

Dość proste.

Wyjaśnienie

}.&.#:
    #:  convert to list of binary digits
  &.    apply right function, then left, then the inverse of right
}.      behead
kapusta
źródło
Zamierzałem opublikować to :(
Cyoce
@Cyoce Me too ...
Adám
4

APL (Dyalog) , 10 bajtów

Funkcja ukrytego przedrostka.

2⊥1↓2∘⊥⍣¯1

Wypróbuj online!

2∘⊥... dekodowania z bazy-2 ...
 ... ⍣¯1 jednej negatywnej czasie (czyli kodowanie w bazie-2)

1↓ upuść pierwszy bit

2⊥ dekodować z base-2

Adám
źródło
4

Rubinowy, 26 bajtów

-7 Bajtów dzięki Ventero. -2 bajty dzięki historicrat.

->n{/./=~'%b'%n;$'.to_i 2}
wyświetlana nazwa
źródło
Możesz zaoszczędzić kilka bajtów, po prostu pomijając pierwszy znak i upuszczając zbędne nawiasy:->n{n.to_s(2)[1..-1].to_i 2}
Ventero
->n{/./=~'%b'%n;$'.to_i 2}
histocrat
4

C (gcc), 38 bajtów

Używany wbudowany gcc.

f(c){return c^1<<31-__builtin_clz(c);}
Colera Su
źródło
Zastąpienie 31-przez ~powinno zaoszczędzić dwa bajty.
@ThePirateBay zależy od sprzętu, czy zmiana jest maskowana. Na moim komputerze wyświetli 0.
Colera Su
4

Montaż ARM, 46 43 bajtów

(Można pominąć rejestr docelowy przy dodawaniu, gdy jest on taki sam jak źródłowy)

clz x1,x0
add x1,1
lsl x0,x1
lsr x0,x1
ret
Michael Dorgan
źródło
Jaki to smak składni zestawu ARM? Mój asembler GNU nie rozumie shr/ shl/ reti zamiast tego chce czegoś takiego jak lsr/ lsl/ bx lr.
Ruslan
Prawdopodobnie miksowanie składni w wielu wersjach (ret pochodzi z aarch64), choć myślałem, że asembler przygotuje je dla ciebie. Jednak w tym przypadku użycie starszego i bezpośredniego lsl / lsr jest prawdopodobnie poprawne.
Michael Dorgan
Zabawne, że mogę to zrobić w 1 operacji mniej, ale rozmiar bajtu wzrasta o 2. Ah kod golfa.
Michael Dorgan,
3

Pyth, 5 bajtów

a^2sl

Zestaw testowy.

Wyjaśnienie:

    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.
źródło
3

Alice , 8 bajtów

./-l
o@i

Wypróbuj online!

Wyjaśnienie

.   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
źródło
3

Japt , 6 bajtów

^2p¢ÊÉ

Wypróbuj online!

Wyjaśnienie

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

Jeśli wprowadzanie 1może się nie powieść: 4 bajty

¢Ån2

Wypróbuj online!

Objaśnienie : pobierz wejściowy binarny ( ¢), odetnij pierwszy znak ( Å), przeanalizuj jako binarny powrót do liczby ( n2).

Justin Mariner
źródło
3

CJam , 7 bajtów

{2b()b}

Wypróbuj online!

Wyjaśnienie:

{     }  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

Ponownie użyj MSB (zawsze 1), aby uniknąć konieczności jego usunięcia; ekwiwalent bez tej sztuczki to {2b1>2b}lub {2b(;2b}.

Esolanging Fruit
źródło
3

Siatkówka , 15 13 bajtów

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

Wypróbuj online!

Wejściowe i wyjściowe w jednostkowym (zestaw testowy dla wygody zawiera konwersję zi na dziesiętny).

Wyjaśnienie

Jest to dość łatwe do zrobienia w pojedynkę. Wszystko, co chcemy zrobić, to usunąć największą moc 2 z wejścia. Możemy dopasować potęgę 2 z niektórymi referencjami. W rzeczywistości łatwiej jest dopasować wartości formularza 2 n -1 , więc zrobimy to i dopasujemy jeden 1 osobno:

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

Grupa 1albo dopasowuje jeden 1na początku, aby rozpocząć, albo dwukrotnie pasuje do tego, co zrobiła podczas ostatniej iteracji. Więc pasuje 1, wtedy 2, wtedy 4i tak dalej. Ponieważ sumy te się sumują, zawsze brakuje nam potęgi 2, którą naprawiamy 1na końcu.

Ze względu na końcowe podawanie linii dopasowanie jest po prostu usuwane z danych wejściowych.

Martin Ender
źródło
3

R , 28 bajtów

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

Wypróbuj online!

Najłatwiej jest obliczyć najbardziej znaczący bit, 2 ^ floor(log2(x))zamiast przeprowadzać podstawowe konwersje, które są dość szczegółowe w R

użytkownik2390246
źródło
3

PARI / GP, 18 bajtów

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

Alternatywne rozwiązanie:

n->n-2^exponent(n)
Charles
źródło
Pierwszy wydaje się dawać złe odpowiedzi. Powinno być n->n-2^logint(n,2)? Drugi nie jest obsługiwany w mojej wersji PARI / GP ani w wersji używanej przez tio.run . Czy to nowa funkcja?
Jeppe Stig Nielsen
@JeppeStigNielsen Ups, naprawione - to właśnie otrzymuję za przesłanie z mojego telefonu. Tak, drugi to nowa funkcja.
Charles
@JeppeStigNielsen, który właśnie sprawdziłem, exponentzostał dodany 5 dni temu, w porównaniu do tego wyzwania, które zostało dodane wczoraj. :)
Charles
3

Haskell , 32 29 bajtów

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

Wypróbuj online!

-3 bajty dzięki @Laikoni

Starsze rozwiązanie, 32 bajty

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

Wypróbuj online!

użytkownik 28667
źródło
1
Funkcje anonimowe są dozwolone, więc nie potrzebujesz f=pierwszego wariantu. Dodatkowo z<-2*y=x!zzapisuje bajt: Wypróbuj online!
Laikoni
3

Excel, 20 bajtów

=A1-2^INT(LOG(A1,2))
IanM_Matrix1
źródło
Witamy na stronie! :)
DJMcMayhem
3

Excel, 36 31 bajtów

-5 bajty dzięki @ IanM_Matrix1

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

Nic interesującego.

Wernisch
źródło
Zmniejsz rozmiar do 31 bajtów, zastępując REPLACE przez MID: = BIN2DEC (MID (DEC2BIN (A1), 2,99))
IanM_Matrix1