Apa nomor bit kebalikannya (biner)?

33

Jadi, Anda diberi nomor basis 10 (desimal) POSITIF . Tugas Anda adalah membalikkan angka biner dan mengembalikan nomor basis 10 itu.

Contoh:

1 => 1 (1 => 1)
2 => 1 (10 => 01)
3 => 3 (11 => 11)
4 => 1 (100 => 001)
5 => 5 (101 => 101)
6 => 3 (110 => 011)
7 => 7 (111 => 111)
8 => 1 (1000 => 0001)
9 => 9 (1001 => 1001)
10 => 5 (1010 => 0101)

Ini adalah tantangan , jadi solusi yang menggunakan byte terkecil menang.

Ini adalah A030101 di OEIS.

juniorRubyist
sumber
2
Apakah "membalikkan bit" berarti membalikkan angka binernya? Terkadang bisa juga berarti membalikkan setiap bit .
ETHproduk
Iya nih. Maaf karena tidak jelas.
juniorRubyist
Ini dan ini mirip veeeeery.
Geobits
OEIS A030101 .
orlp
1
"base 10" Ada alasan khusus mengapa?
CalculatorFeline

Jawaban:

20

Python , 29 byte

lambda n:int(bin(n)[:1:-1],2)

Cobalah online!

Ini adalah fungsi anonim dan tidak bernama yang mengembalikan hasilnya.


Pertama, bin(n)ubah argumen menjadi string biner. Kami biasanya akan membalikkan ini dengan notasi slice [::-1]. Ini membaca string dengan langkah -1 , yaitu mundur. Namun, string biner dalam Python diawali dengan 0b, dan oleh karena itu kami memberikan argumen kedua slicing sebagai 1 , mengatakan Python untuk membaca mundur berakhir pada indeks 1 , sehingga tidak membaca indeks 1 dan 0 .

Sekarang kita memiliki string biner mundur, kita meneruskannya int(...)dengan argumen kedua sebagai 2 . Ini membaca string sebagai integer basis 2, yang kemudian implikasinya dikembalikan oleh ekspresi lambda.

FlipTack
sumber
2
Kalahkan Anda 9 detik.
mbomb007
6
@ mbomb007 jadi jawaban saya tidak valid karena Anda mengklik tombol posting 9 detik sebelumnya? Hanya karena kami mencapai golf yang sama pada saat yang sama tidak berarti kami harus menghapus jawaban apa pun. Jika ada, salahkan pertanyaan 0-upaya.
FlipTack
3
Bukan tidak valid, tapi jelas tidak ada gunanya. Jika saya lebih lambat, saya hanya akan menghapus saya dan mengirim komentar pada yang lebih cepat yang saya hasilkan juga.
mbomb007
1
@steenbergh Siapa yang peduli? Kode yang sama, skor yang sama.
mbomb007
17

Python, 29 byte

lambda n:int(bin(n)[:1:-1],2)

Cobalah online

mbomb007
sumber
1
Inilah yang akan saya lakukan. ;)
juniorRubyist
13

JavaScript (ES6), 30 28 byte

Disimpan 2 byte berkat @Arnauld

f=(n,q)=>n?f(n>>1,q*2|n%2):q

Ini pada dasarnya menghitung bit mundur satu per satu: Kita mulai dengan q = 0 ; sementara n bernilai positif, kita mengalikan q dengan 2, memutuskan bit terakhir dari n dengan n>>1, dan menambahkannya ke q dengan |n%2. Ketika n mencapai 0, angka telah berhasil dibalik, dan kami mengembalikan q .

Berkat nama bawaan JS yang panjang, menyelesaikan tantangan ini dengan cara mudah membutuhkan 44 byte:

n=>+[...n.toString(2),'0b'].reverse().join``

Menggunakan rekursi dan string, Anda bisa mendapatkan solusi 32 byte yang melakukan hal yang sama:

f=(n,q='0b')=>n?f(n>>1,q+n%2):+q
Produksi ETH
sumber
f=(n,q)=>n?f(n>>1,q*2|n%2):qhampir berhasil. Tapi sayangnya tidak untuk n=0.
Arnauld
@Arnauld OP belum menjawab apakah input akan selalu positif, tetapi jika demikian, maka 0 tidak harus ditangani.
FlipTack
Ini adalah tindak lanjut terlambat, tetapi input sekarang dikenal selalu positif.
Arnauld
@Arnauld Terima kasih!
ETHproduksi
10

Java 8, 53 47 46 45 byte

  • -4 byte terima kasih kepada Titus
  • -1 byte terima kasih kepada Kevin Cruijssen

Ini adalah ungkapan lambda yang memiliki prinsip yang sama dengan jawaban ETH (walaupun rekursi terlalu bertele-tele di Jawa, jadi kami menggunakan loop):

x->{int t=0;for(;x>0;x/=2)t+=t+x%2;return t;}

Cobalah online!

Ini dapat ditugaskan dengan IntFunction<Integer> f = ..., dan kemudian dipanggil dengan f.apply(num). Diperluas, tidak diserang, dan dikomentari, terlihat seperti ini:

x -> { 
    int t = 0;           // Initialize result holder   
    while (x > 0) {      // While there are bits left in input:
        t <<= 1;         //   Add a 0 bit at the end of result
        t += x%2;        //   Set it to the last bit of x
        x >>= 1;         //   Hack off the last bit of x
    }              
    return t;            // Return the final result
};
FlipTack
sumber
1
Simpan 3 byte dengan t*2alih - alih (t<<1), satu lagi dengan memindahkan perhitungan itu dari loop head ke loop body. Bisakah Anda menggunakan xbukan x>0untuk kondisinya?
Titus
2
@Titus bukan tanpa pemeran eksplisit ke boolean, tapi terima kasih atas tips lainnya! Juga baru menyadari bahwa x>>=1dapat diganti dengan x/=2karena akan secara otomatis menjadi divisi integer.
FlipTack
45 byte (Diubah t=t*2+ke t+=t+.)
Kevin Cruijssen
@KevinCruijssen bagus!
FlipTack
9

J, 6 byte

|.&.#:

|. membalikkan

&. dibawah

#: basis 2

Adm
sumber
8

Jelly , 3 byte

BUḄ

Cobalah online!

B   # convert to binary
 U  # reverse
  Ḅ # convert to decimal
Riley
sumber
7
Itu cukup singkat,
BUB
Hmm ... Apakah itu benar-benar 3 byte ?
aioobe
1
@aioobe Yap. Jelly menggunakan halaman kode sendiri di mana masing-masing karakter ini 1 byte.
Riley
Keren Terimakasih! <pad>
aioobe
8

Mathematica, 19 byte

#~IntegerReverse~2&
ngenisis
sumber
7

Labirin, 23 byte

?_";:_2
  :   %
 @/2_"!

Yah, ini aneh ... ini mengembalikan nomor BINARY terbalik ... Terima kasih @Martin Ender karena menunjukkan bug saya dan kesalahan ID 10T saya. Jadi ini tidak berhasil, saya harus mencari solusi lain.

C Anderson
sumber
1
Selamat datang di PPCG, dan posting pertama yang bagus! Hanya menyelesaikan tantangan dalam bahasa seperti Labirin bisa sangat sulit. Di sekitar sini, kami biasanya mengawali baris pertama dari jawaban dengan satu atau dua hash, untuk membuatnya ditampilkan sebagai tajuk:# Labyrinth, 89 bytes
ETHproduksi
1
Apakah Anda secara tidak sengaja menghilangkan spasi terdepan dari baris kedua? Seperti berdiri, program ini hanya akan bolak-balik di baris pertama karena _ada di persimpangan.
Martin Ender
Sayangnya, saya hanya memperhatikan bahwa ini tidak valid, karena tantangannya meminta representasi basis-10 dari angka terbalik, bukan representasi binernya.
Martin Ender
6

C, 48 44 43 42 byte

-1 byte berkat gurka dan -1 byte terima kasih kepada anatolyg:

r;f(n){for(r=n&1;n/=2;r+=r+n%2);return r;}

Solusi 44 byte sebelumnya:

r;f(n){r=n&1;while(n/=2)r=2*r+n%2;return r;}

Solusi 48 byte sebelumnya:

r;f(n){r=0;while(n)r=2*(r+n%2),n/=2;return r/2;}

Tidak digabungkan dan digunakan:

r;
f(n){
 for(
  r=n&1;
  n/=2;
  r+=r+n%2
 );
 return r;}
}


main() {
#define P(x) printf("%d %d\n",x,f(x))
P(1);
P(2);
P(3);
P(4);
P(5);
P(6);
P(7);
P(8);
P(9);
P(10);
}
Karl Napf
sumber
Isn't r already initialized to zero here r;f(n){r=0;, e.g. the r=0; is unnecessary? Also minor typo: "Previous 48 bytes solution"
simon
1
@gurka The function should be reusable.
Karl Napf
1
I think that for loops are always at least as short as while loops, and often shorter.
anatolyg
@anatolyg something like: r;f(n){for(r=n&1;n/=2;r=2*r+n%2);return r;}? 1 byte shorter, but I'm unsure if it's valid C (C99).
simon
Yes; also, turn = into += to make it shorter and more obfuscated
anatolyg
5

Ruby, 29 28 bytes

->n{("%b"%n).reverse.to_i 2}

"%b" % n formats the input n as a binary string, reverse, then convert back to a number

Usage/Test cases:

m=->n{("%b"%n).reverse.to_i 2}
m[1] #=> 1
m[2] #=> 1
m[3] #=> 3
m[4] #=> 1
m[5] #=> 5
m[6] #=> 3
m[7] #=> 7
m[8] #=> 1
m[9] #=> 9
m[10] #=> 5
Alexis Andersen
sumber
@Titus I think you misunderstand the answer. 2 is the base he is converting to, and n is the input. ->args{return value} is the ruby lambda syntax
Cyoce
Can you remove the parentheses in .to_i(2)?
Cyoce
@Cyoce sure enough, thanks.
Alexis Andersen
4

Java (OpenJDK), 63 bytes

a->a.valueOf(new StringBuffer(a.toString(a,2)).reverse()+"",2);

Try it online!

Thanks to poke for -12 bytes and to Cyoce for -8 bytes!

Pavel
sumber
Even though REPL submissions are allowed, they still follow the rule that you can't assume input is in predefined variables (like a in this context)
FlipTack
@FlipTack Oops. It was originally a function before I remembered the repl existed
Pavel
1
Also, in the future, use print instead of println for golfing :)
FlipTack
1
StringBuffer saves a byte over StringBuilder
Poke
1
Could you do +"" instead of .toString()?
Cyoce
3

Perl 6, 19 bytes

{:2(.base(2).flip)}
Sean
sumber
Where is the input?
Titus
This is a function that takes a single parameter $_. It isn't mentioned by name, but the base method is called on it.
Sean
2
@Titus in Perl 6 a Block is a type of Code, which is to say it's a callable object. The above is an expression that you can take and assign to a variable like a function or lambda in another language, or call directly — {:2(.base(2).flip)}(10) at the REPL will print 5. So it meets the standard code-golf criteria for a function.
hobbs
3

Haskell, 36 bytes

0!b=b
a!b=div a 2!(b+b+mod a 2)
(!0)

Same algorithm (and length!) as ETHproductions’ JavaScript answer.

Lynn
sumber
3

Bash/Unix utilities, 24 23 bytes

dc -e2i`dc -e2o?p|rev`p

Try it online!

Mitchell Spector
sumber
A courageous take on Bash! 😉
juniorRubyist
@juniorRubyist -- Thank you!
Mitchell Spector
3

PHP, 33 bytes

<?=bindec(strrev(decbin($argn)));

convert to base2, reverse string, convert to decimal. Save to file and run as pipe with -F.

no builtins:

iterative, 41 bytes

for(;$n=&$argn;$n>>=1)$r+=$r+$n%2;echo$r;

While input has set bits, pop a bit from input and push it to output. Run as pipe with -nR.

recursive, 52 bytes

function r($n,$r=0){return$n?r($n>>1,$r*2+$n%2):$r;}
Titus
sumber
@JörgHülsermann The 44 bytes have $r+=$r. But I actually don´t remember why I put that in front.
Titus
2

MATL, 4 bytes

BPXB

Try it online!

Explanation

B     % Input a number implicitly. Convert to binary array
P     % Reverse array
XB    % Convert from binary array to number. Display implicitly
Luis Mendo
sumber
2

Pyth, 6 bytes

i_.BQ2

Test suite available here.

Explanation

i_.BQ2
    Q     eval(input())
  .B      convert to binary
 _        reverse
i    2    convert from base 2 to base 10
Mike Bufardeci
sumber
2

Japt, 5 bytes

¢w n2

Try it Online!

Oliver
sumber
1
Nice, exactly what I had. The ) could be a space too :-)
ETHproductions
2

Scala, 40 bytes

i=>BigInt(BigInt(i)toString 2 reverse,2)

Usage:

val f:(Int=>Any)=i=>BigInt(BigInt(i)toString 2 reverse,2)
f(10) //returns 5

Explanation:

i =>          // create an anonymous function with a parameter i
  BigInt(       //return a BigInt contructed from
    BigInt(i)     //i converted to a BigInt
    toString 2    //converted to a binary string
    reverse       //revered
    ,           
    2             //interpreted as a binary string
  )
corvus_192
sumber
1

Mathematica, 38 bytes

#+##&~Fold~Reverse[#~IntegerDigits~2]&
JungHwan Min
sumber
1

Groovy, 46 bytes

{0.parseInt(0.toBinaryString(it).reverse(),2)}
Magic Octopus Urn
sumber
Does this take any input?
Titus
1
@Titus it refers to the argument given to a block IIRC
Cyoce
I love how this is the same length as my Java answer - Java and groovy, unite!
FlipTack
1
@FlipTack I'm gonna go cry now.
Magic Octopus Urn
1

CJam, 8 bytes

ri2bW%2b

Try it online!

Explanation

ri          e# Read integer
  2b        e# Convert to binary array
    W%      e# Reverse array
      2b    e# Convert from binary array to number. Implicitly display
Luis Mendo
sumber
1

Batch, 62 bytes

@set/an=%1/2,r=%2+%1%%2
@if %n% gtr 0 %0 %n% %r%*2
@echo %r%

Explanation: On the first pass, %1 contains the input parameter while %2 is empty. We therefore evaluate n as half of %1 and r as +%1 modulo 2 (the % operator has to be doubled to quote it). If n is not zero, we then call ourselves tail recursively passing in n and an expression that gets evaluated on the next pass effectively doubling r each time.

Neil
sumber
1

C#, 98 bytes

using System.Linq;using b=System.Convert;a=>b.ToInt64(string.Concat(b.ToString(a,2).Reverse()),2);
Horváth Dávid
sumber
1

R, 55 bytes

sum(2^((length(y<-rev(miscFuncs::bin(scan()))):1)-1)*y)

Reads input from stdin and consequently uses the bin function from the miscFuncs package to convert from decimal to a binary vector.

Billywob
sumber
1

Pushy, 19 bytes

No builtin base conversion!

$&2%v2/;FL:vK2*;OS#

Try it online!

Pushy has two stacks, and this answer makes use of this extensively.

There are two parts two this program. First, $&2%v2/;F, converts the number to its reverse binary representation:

            \ Implicit: Input is an integer on main stack.
$      ;    \ While i != 0:
 &2%v       \   Put i % 2 on auxiliary stack
     2/     \   i = i // 2 (integer division)
        F   \ Swap stacks (so result is on main stack)

Given the example 10, the stacks would appear as following on each iteration:

1: [10]
2: []

1: [5]
2: [0]

1: [2]
2: [0, 1]

1: [1]
2: [0, 1, 0]

1: [0]
2: [0, 1, 0, 1]

We can see that after the final iteration, 0, 1, 0, 1 has been created on the second stack - the reverse binary digits of 10, 0b1010.

The second part of the code, L:vK2*;OS#, is taken from my previous answer which converts binary to decimal. Using the method decsribed and explained in that answer, it converts the binary digits on the stack into a base 10 integer, and prints the result.

FlipTack
sumber
0

k, 18 bytes

{2/:|X@&|\X:0b\:x}

Example:

k){2/:|X@&|\X:0b\:x}6
3
skeevey
sumber
0

C#, 167 bytes

 for(int i = 1; i <= 10; i++)
 {
 var bytes= Convert.ToString(i, 2);
 var value= Convert.ToInt32(byteValue.Reverse()); 
 console.WriteLine(value);
}

Explanation:

Here I will iterate n values and each time iterated integer value is convert to byte value then reverse that byte value and that byte value is converted to integer value.

Deepak
sumber
1
Welcome to the site! I don't know much about C# but you most certainly have a good deal of extra whitespace I would recommend removing. It also is not clear how I/O is dealt with in this submission. It is standard to either write a function or to use STDIN (I think that is console.Read() but you would probably know better than I would) and STDOUT. Anyway, welcome to the site if you want more experienced advice in golfing C# I would recommend codegolf.stackexchange.com/questions/173/…
Wheat Wizard
I've downvoted this answer, because it doesn't work at all. .Reverse() returnes IEnumerable<char>. As Convert.ToInt32 doesn't have an overload for IEnumerable it throws an exception. Also the answer doesn't follow the rules for code golf: 1)As nothing is specified the submission has to be a full program or function not just a snippet. 2)using statements must be included in the byte count
raznagul
0

c/c++ 136 bytes

uint8_t f(uint8_t n){int s=8*sizeof(n)-ceil(log2(n));n=(n&240)>>4|(n&15)<<4;n=(n&204)>>2|(n&51)<<2;n=(n&172)>>1|(n&85)<<1;return(n>>s);}

It's not going to win, but I wanted to take a different approach in c/c++ 120 bytes in the function

#include <math.h>
#include <stdio.h>
#include <stdint.h>

uint8_t f(uint8_t n){
    int s=8*sizeof(n)-ceil(log2(n));
    n=(n&240)>>4|(n&15)<<4;
    n=(n&204)>>2|(n&51)<<2;
    n=(n&172)>>1|(n&85)<<1;
    return (n>>s);
}

int main(){
    printf("%u\n",f(6));
    return 0;
}

To elaborate on what I am doing, I used the log function to determine the number of bits utilized by the input. Than a series of three bit shifts left/right, inside/outside, even/odd which flips the entire integer. Finally a bit shift to shift the number back to the right. Using decimals for bit shifts instead of hex is a pain but it saved a few bytes.

mreff555
sumber
You do need to include the function declaration, so this is actually 163 bytes. Although, if you remove the extraneous whitespace, you could shorten it to 136.
DJMcMayhem