Menghapus bit paling signifikan dari integer

29

Memasukkan

Inputnya adalah bilangan bulat positif tunggal n

Keluaran

Output ndengan bit set paling signifikan untuk 0.

Uji Kasus

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

Sebagai contoh: 350dalam biner adalah 101011110. Mengatur bit yang paling signifikan (yaitu 1bit paling kiri ) untuk 0mengubahnya menjadi 001011110yang setara dengan bilangan bulat desimal 94, output. Ini adalah OEIS A053645 .

Marcus Andrews
sumber
19
Menghapus sedikit yang paling signifikan dari 10jelas memberi 0: D
clabacchio
@clabacchio I .. it ... er ... wha? (bagus)
Baldrickk
12
Tampak bagi saya bahwa nol sama pentingnya dengan yang ada. Ketika Anda mengatakan "bit paling signifikan" yang Anda maksudkan adalah "bit paling signifikan yang disetel menjadi satu".
Michael Kay

Jawaban:

12

C (gcc) , 49 44 40 39 byte

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

Cobalah online!

Cleblanc
sumber
1
Anda dapat mengganti i<=ndengan n/iuntuk -1 byte. Ini bukan golf saya, orang lain mencoba mengeditnya di posting Anda, tetapi saya gulung balik karena suntingan untuk posting golf tidak diterima sesuai dengan aturan komunitas kami.
HyperNeutrino
1
@HyperNeutrino Saya melihat dan menyetujui hasil edit tadi. Tidak mengetahui aturan itu, tetapi ini tip golf yang bagus!
cleblanc
Ah baiklah. Ya biasanya orang seharusnya mengirim komentar untuk tips golf dan OP harus melakukan pengeditan, tetapi jika Anda menerimanya, itu tidak terlalu menjadi masalah. :)
HyperNeutrino
10

Python 2 , 27 byte

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

Cobalah online!

26 byte

Sayangnya, ini tidak berfungsi untuk 1:

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

Cobalah online!

FlipTack
sumber
9

05AB1E , 5 byte

.²óo-

Cobalah online!

Menghapus bit paling signifikan dari integer N setara dengan menemukan jarak dari N ke kekuatan bilangan bulat tertinggi 2 lebih rendah dari N .

Jadi, saya menggunakan rumus N - 2 lantai (log 2 N) :

  • - Logaritma dengan basis 2 .
  • ó - Lantai ke bilangan bulat.
  • o- 2 dinaikkan menjadi kekuatan hasil di atas.
  • - - Perbedaan.
Tuan Xcoder
sumber
1
b¦Cjuga berfungsi ... bukan? Konversi ke biner, MSB selalu di indeks 1, hapus MSB, konversikan kembali.
Magic Octopus Mm
2
@ MagicOctopusUrn Tidak ada yang salah, gagal untuk 1!
Tn. Xcoder
8

Jelly , 3 byte

BḊḄ

Cobalah online!

Penjelasan

BḊḄ  Main Link
B    Convert to binary
 Ḋ   Dequeue; remove the first element
  Ḅ  Convert from binary
HyperNeutrino
sumber
2
Bukankah dan codepoint dua byte? Ini akan mengubah ukuran keseluruhan menjadi 5 byte.
Bartek Banachewicz
3
@BartekBanachewicz Jelly menggunakan codepage sendiri , di mana karakter itu hanya 1 byte.
steenbergh
1
Terima kasih telah bertanya dan menjawab ini, itu telah menyadap saya sejak lama!
Ukko
8

C (gcc) - 59 byte

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

Jawaban gcc ini hanya menggunakan operasi bitwise dan aritmatika integer. Tidak ada logaritma di sini! Mungkin memiliki masalah dengan input 0, dan benar-benar non-portabel.

Ini jawaban pertama saya di situs ini, jadi saya suka umpan balik dan peningkatan. Saya yakin bersenang-senang dengan belajar ekspresi bitwise.

Charles Diploma
sumber
1
Selamat datang di PPCG, dan jawaban pertama yang bagus! Kami harap Anda menikmati berpartisipasi dalam lebih banyak tantangan :-)
ETHproduk
Anda tidak memerlukan program lengkap dengan main, suatu fungsi adalah pengiriman yang valid . Mengubah ini menjadi fungsi dan mengambil input sebagai argumen ke fungsi mengatakan menghemat 18 byte .
Steadybox
1
Anda bahkan bisa menulisnya sebagai makro untuk menyimpan dua byte lagi .
Steadybox
7

MATL , 8 6 byte

B0T(XB

Cobalah online!

Disimpan dua byte berkat Cinaski. Beralih ke pengindeksan tugas alih-alih pengindeksan referensi lebih pendek 2 byte :)

Penjelasan:

          % 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
sumber
1
Anda bisa menggunakan pengindeksan referensi (juga untuk 6 byte), jika Anda menggunakan 4Lbukan [2J]. tZlcW-
Kesenangan
6

Java (OpenJDK 8) , 23 byte

n->n^n.highestOneBit(n)

Cobalah online!

Maaf, bawaan: - /

Olivier Grégoire
sumber
Java dengan built-in yang beberapa bahasa populer lainnya seperti .NET dan Python belum ?! o.Ô memberi +1 pada itu. Akan memposting sesuatu yang lebih lama tanpa build-in .. Milik Anda lebih pendek 15 byte. XD
Kevin Cruijssen
@KevinCruijssen Sesuatu seperti n->n^1<<(int)Math.log2(n)akan berfungsi dan kemungkinan lebih pendek dari 38 byte. Itu adalah ide saya yang kedua (belum teruji), jika yang highestOneBitsatu tidak bekerja dengan tepat. Karena penasaran, apa solusi Anda
Olivier Grégoire
Tambang itu n->n^1<<(int)(Math.log(n)/Math.log(2))karena Math.log2tidak ada di Jawa. ; P Hanya Math.log, Math.log10dan Math.loglptersedia.
Kevin Cruijssen
2
Saya akan memposting yang sama, hanya minus bukan xor. Teringat metode dari ini
JollyJoker
1
@KevinCruijssen Ups, Math.log2memang tidak ada ... Buruk saya. Lihat? Satu metode yang bagus ( highestOneBit) ada tetapi tidak ada yang lain ( Math.log2). Java aneh ;-)
Olivier Grégoire
6

Sekam , 3 byte

ḋtḋ

Cobalah online!

Penjelasan:

    -- 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
sumber
Sama halnya dengan solusi Jelly, sepertinya ini sebenarnya 5 byte, bukan 3.
Bartek Banachewicz
1
@BartekBanachewicz Demikian pula untuk Jelly, sekam menggunakan codepage sendiri, jadi ini adalah benar-benar 3 byte: P
HyperNeutrino
@BartekBanachewicz Lihat di sini untuk codepage: github.com/barbuz/Husk/wiki/Codepage
Laikoni
5

Python 2 , 27 byte

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

Cobalah online!

Penjelasan

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
sumber
... Tepat ketika saya sedang mengerjakan perhitungan bitwise. : P
totallyhuman
@totallyhuman heh maaf tapi mengalahkan kamu untuk itu: P
HyperNeutrino
2**len(bin(n))/8bisa juga dieja 1<<len(bin(n))-3, dan kemudian akan berfungsi di 2 dan 3 (tidak ada byte yang disimpan / ditambahkan).
Mego
@Mego Cool, terima kasih untuk tambahannya!
HyperNeutrino
5

Python 3 , 30 byte

-8 Bytes berkat caird coinheringaahing. Saya mengetiknya dari memori. :Hai

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

Cobalah online!

benar-benar manusiawi
sumber
Mengapa tidak lambda n:int(bin(n)[3:],2)?
caird coinheringaahing
Ya, a) itu akan salah pada 1 , b) Aku cukup bodoh untuk tidak memikirkan itu. Tapi saya memperbaikinya dengan perubahan kecil. Terima kasih!
totallyhuman
Saya telah mengedit kode sehingga berfungsi, (dan menyimpan 4 byte)
caird coinheringaahing
Itu masih salah pada 1 .
totallyhuman
@cairdcoinheringaahing Itu adalah jawaban asli saya , tetapi kemudian saya menyadari kesalahannya pada 1. Pemecahan masalah berakhir lebih lama daripada metode XOR sederhana
FlipTack
4

Mathematica, 37 byte

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

Cobalah online!

J42161217
sumber
4

JavaScript, 22 20 byte

Disimpan 2 byte berkat ovs

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

Cobalah online!

Pendekatan lain, 32 byte

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

Cobalah online!


sumber
mengapa kamu lakukan .slice`1`^0ketika .slice(1)^0akan bekerja dengan baik, haha
ETHproduksi
@ ETHproductions. Yang ini terlihat lebih baik :)
4

J, 6 byte

}.&.#:

Cukup mudah.

Penjelasan

}.&.#:
    #:  convert to list of binary digits
  &.    apply right function, then left, then the inverse of right
}.      behead
cole
sumber
Saya akan memposting ini :(
Cyoce
@Cyoce Me too ...
Adám
4

APL (Dyalog) , 10 byte

Fungsi awalan Tacit.

212∘⊥⍣¯1

Cobalah online!

2∘⊥... decode dari base-2 ...
 ... ⍣¯1 negative one time (mis. Encode di base-2)

1↓ jatuhkan bit pertama

2⊥ decode dari base-2

Adm
sumber
4

Ruby, 26 byte

-7 Bytes terima kasih kepada Ventero. -2 Bytes berkat historrat.

->n{/./=~'%b'%n;$'.to_i 2}
nama tampilan
sumber
Anda dapat menyimpan beberapa byte hanya dengan melewatkan karakter pertama dan menjatuhkan tanda kurung berlebihan:->n{n.to_s(2)[1..-1].to_i 2}
Ventero
->n{/./=~'%b'%n;$'.to_i 2}
histokrat
4

C (gcc), 38 byte

Built-in gcc digunakan.

f(c){return c^1<<31-__builtin_clz(c);}
Colera Su
sumber
Mengganti 31-dengan ~harus menghemat dua byte.
@ThePirateBay tergantung pada perangkat keras apakah shift tersebut ditutup. Di komputer saya, itu akan menampilkan 0.
Colera Su
4

Majelis ARM, 46 43 byte

(Anda dapat menghilangkan register tujuan pada add ketika sama dengan sumber)

clz x1,x0
add x1,1
lsl x0,x1
lsr x0,x1
ret
Michael Dorgan
sumber
Apa rasa sintaks perakitan ARM ini? GNU assembler saya tidak mengerti shr/ shl/ retdan ingin bukan sesuatu seperti lsr/ lsl/ bx lr.
Ruslan
Mungkin mencampur sintaks di beberapa versi (ret adalah dari aarch64), meskipun saya berpikir bahwa assembler akan pseudo op ini untuk Anda. Untuk keperluan di sini, menggunakan lsl / lsr yang lebih lama dan langsung mungkin benar.
Michael Dorgan
Lucunya, saya bisa melakukannya dalam 1 operasi kurang, tapi saya ukuran byte naik 2. Ah kode golf.
Michael Dorgan
3

Pyth, 5 byte

a^2sl

Suite uji.

Penjelasan:

    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.
sumber
3

Alice , 8 byte

./-l
o@i

Cobalah online!

Penjelasan

.   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
sumber
3

Japt , 6 byte

^2p¢ÊÉ

Cobalah online!

Penjelasan

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

Jika input 1dapat gagal: 4 byte

¢Ån2

Cobalah online!

Penjelasan : dapatkan biner input ( ¢), iris dulu char ( Å), parse sebagai biner kembali ke angka ( n2).

Justin Mariner
sumber
3

CJam , 7 byte

{2b()b}

Cobalah online!

Penjelasan:

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

Gunakan kembali MSB (yang selalu 1) untuk menghindari keharusan menghapusnya; yang setara tanpa trik itu adalah {2b1>2b}atau {2b(;2b}.

Buah Esolanging
sumber
3

Retina , 15 13 byte

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

Cobalah online!

Input dan output dalam unary (test suite mencakup konversi dari dan ke desimal untuk kenyamanan).

Penjelasan

Ini cukup mudah dilakukan di unary. Yang ingin kami lakukan adalah menghapus kekuatan 2 terbesar dari input. Kami dapat mencocokkan kekuatan 2 dengan beberapa referensi ke depan. Sebenarnya lebih mudah untuk mencocokkan nilai dari formulir 2 n -1 , jadi kami akan melakukannya dan mencocokkan satu 1 secara terpisah:

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

Grup 1dapat mencocokkan satu 1di awal untuk memulai sesuatu, atau cocok dengan dua kali apa yang dilakukan pada iterasi terakhir. Jadi itu cocok 1, lalu 2, kemudian 4dan seterusnya. Karena ini ditambahkan, kami selalu kekurangan 2, yang kami perbaiki dengan 1pada akhirnya.

Karena mengikuti garis makan, pertandingan hanya dihapus dari input.

Martin Ender
sumber
3

R , 28 byte

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

Cobalah online!

Cara termudah untuk menghitung bit paling signifikan melalui 2 ^ floor(log2(x))daripada melakukan konversi basis, yang cukup bertele-tele dalam R

pengguna2390246
sumber
3

PARI / GP, 18 byte

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

Solusi alternatif:

n->n-2^exponent(n)
Charles
sumber
Yang pertama sepertinya memberikan jawaban yang salah. Haruskah begitu n->n-2^logint(n,2)? Yang kedua tidak didukung dalam versi PARI / GP saya, atau dalam versi yang digunakan oleh tio.run . Apakah itu fungsi baru?
Jeppe Stig Nielsen
@JeppeStigNielsen Ups, sudah diperbaiki - itulah yang saya dapatkan dari pengiriman ponsel saya. Ya, yang kedua adalah fungsi baru.
Charles
@JeppeStigNielsen yang baru saya periksa, exponentditambahkan 5 hari yang lalu, dibandingkan dengan tantangan ini yang ditambahkan kemarin. :)
Charles
3

Haskell , 32 29 byte

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

Cobalah online!

-3 byte terima kasih kepada @Laikoni

Solusi yang lebih lama, 32 byte

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

Cobalah online!

pengguna28667
sumber
1
Fungsi anonim diizinkan, jadi Anda tidak memerlukan f=varian pertama. Selain itu z<-2*y=x!zmenyimpan byte: Cobalah secara online!
Laikoni
3

Excel, 20 byte

=A1-2^INT(LOG(A1,2))
IanM_Matrix1
sumber
Selamat datang di situs ini! :)
DJMcMayhem
3

Excel, 36 31 byte

-5 byte terima kasih kepada @ IanM_Matrix1

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

Tidak ada yang menarik.

Wernisch
sumber
Kurangi ukuran menjadi 31 byte dengan mengganti REPLACE dengan MID: = BIN2DEC (MID (DEC2BIN (A1), 2,99))
IanM_Matrix1