Nomor popcount ajaib

25

Ada algoritma rumit yang terkenal untuk menghitung jumlah bit yang ditetapkan dalam integer 32-bit unsigned:

int popcount(unsigned x) {
   x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
   x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
   x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
   x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF);
   return x;
}

Saya tidak akan menjelaskannya di sini. Tapi bayangkan kode serupa untuk bilangan bulat 512-bit! Konstanta heksadesimal akan besar, dan membentuk pola yang cantik. Tugas Anda hanyalah untuk mencetak hasil yang persis seperti ini :

0x55555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555
0x33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
0x00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff
0x0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff
0x00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff
0x0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff
0x00000000000000000000000000000000ffffffffffffffffffffffffffffffff00000000000000000000000000000000ffffffffffffffffffffffffffffffff
0x0000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

Tolong, tidak ada spasi tambahan - meskipun satu baris tambahan baru opsional.

Ini adalah , jadi jawaban tersingkat (dalam byte) menang.

Lynn
sumber
Apakah kami diizinkan mengambil input (seperti pada sesuatu seperti 0x0x0x0x0x0x0x0x0x)?
ouflak
@ouflak No. ———
Lynn

Jawaban:

3

05AB1E , 26 22 21 byte

05AB1E menggunakan pengkodean CP-1252 .

9F„0x0NÍo×9ooNoo>÷hJ,

Cobalah online!

Penjelasan

9F                      # for N in [0 ... 8]
  „0x                   # push the string "0x"
     0NÍo×              # push 2**(N-2) zeroes
          9oo           # 2**2**9
                 ÷      # //
             Noo>       # (2**2**N+1)
                  h     # converted to base-16
                   J    # join everything to string
                    ,   # print with a newline

Versi lain yang mungkin ditingkatkan

9F9ooNoo>÷h¾6o×J7o£R…0xÿ,
9F9ooNoo>÷h0žy×ìR7o£R…0xÿ,
9FX0No×1No×JCh7o×1K7o£…0xÿ,
8ÝovX0y×1y×JCh7o×1K7o£…0xÿ,
9F1NoÅ0D>)˜JCh1K7o×7o£…0xÿ,
Emigna
sumber
21

Python 2, 52 49 46 byte

Nomor k diberikan oleh 2**512/(2**2**k + 1). Ini untuk nomor 512 bit, jadi sepele untuk memperluas pola ke lebar yang berbeda.

l=2;exec"print'0x%0128x'%(2**512/-~l);l*=l;"*9

3 byte disimpan berkat Dennis.
3 byte disimpan berkat xnor.

orlp
sumber
2
Keuntungan bilangan bulat presisi arbitrer ...
ETHproduk
Bagus. Ini menghemat beberapa byte.
Dennis
Lebih pendek untuk tetap mengkuadratkan:l=2;exec"print'0x%0128x'%(2**512/-~l);l*=l;"*9
xnor
1
Itu menghangatkan hati saya melihat Python di voting-lead :)
Tobias Kienzler
4
@ TuukkaX Saya hanya punya banyak pengalaman dengan hacks yang sedikit memutarbalikkan. Saya menggunakan Wolfram Alpha banyak untuk menyederhanakan jumlah dan semacamnya. Tapi pada dasarnya saya membuat pola 01010101, 00010001, 00000001, dan kemudian dikalikan tersebut dengan 1, 11, 1111untuk mendapatkan pola biner yang benar. Misalnya 01010101Anda bisa mendapatkan rumus untuk lebar tertentu dengan melakukan sum 2^(2*k) for k = 0, w/2 - 1dan mencari tahu itu (2**w - 1)/3.
orlp
7

PHP, 111 110 108 byte

Satu byte disimpan berkat @ user59178.

<?=($p=str_pad)("0x",130,5).$p($s="\n0x",131,3);for($x=1;$x<65;$x*=2)echo($p($s,131,$p(0,$x,0).$p(f,$x,f)));

Apa pola untuk 1024 bit? : D

Titus
sumber
1
Anda dapat menyimpan byte dengan menggunakan $x<65daripada $i++<7. Kali ini saya mengujinya dan semuanya.
user59178
6

Retina , 43 byte

:`
0x128$*5
:`5
3
;{:`33
0f
0(f+)(0+)
0$2$1

Cobalah online!

Penjelasan

Ini membuat banyak penggunaan :opsi yang umumnya kurang digunakan yang memungkinkan Anda mencetak hasil antara, karena jauh lebih pendek untuk memodifikasi satu baris daripada untuk membangun seluruh output.

:`
0x128$*5

Ini menggantikan input kosong dengan 0xdiikuti oleh 128 5s dan mencetaknya untuk menghasilkan baris pertama.

:`5
3

Yang ini menggantikan 5s dengan 3s untuk menghasilkan baris kedua dan mencetaknya juga.

;{:`33
0f

Ini adalah baris khusus-cased terakhir dan mengubah setiap dua 3menjadi 0funtuk menghasilkan baris ketiga. Ini juga memulai perulangan melalui dua tahap terakhir ( {). Namun, tahap ini tidak akan melakukan apa pun setelah iterasi pertama kecuali mencetak keadaan saat ini. The ;menekan output pada akhir program untuk menghindari duplikasi baris terakhir.

0(f+)(0+)
0$2$1

Substitusi ini sekarang mengubah setiap baris ke baris berikutnya, dengan menukar setiap pasangan fs dan 0s lainnya. Kondisi "setiap pasangan lain" diberlakukan dengan mencocokkan nol di depan f, yang membuat tidak mungkin untuk mencocokkan pasangan berturut-turut karena pertandingan tidak dapat tumpang tindih.

Martin Ender
sumber
6

Vim, 32 byte

i5<CR>3<Esc>qqYpVrf$<C-V>{yPG1vr0q6@q<C-V>{I0x<Esc>

Saya hanya perlu secara manual menulis yang pertama 5dan 3, dan makro menangani sisanya, "menggandakan jumlah bit" setiap kali berjalan. Urutan langkah-langkah di makro agak aneh (buat fbaris baru , salin blok-bijaksana, gunakan kembali ukuran blok visual untuk menempatkan 0s di fbaris), tapi itu varian tercepat yang saya temukan.

udioica
sumber
5

Pyth, 26 byte

V9%"0x%0128x"/^2 512h^2^2N

Port jawaban Python saya.

orlp
sumber
5

J, 46 34 byte

Saya sedang berusaha bermain golf ini, tetapi bayi ini suka tinggal di 46 byte ... Tidak lagi! -12 bytes terima kasih kepada mil!

'0x',"1'5','3','0f'(128$#)"{~2^i.7

Cobalah online! : D

Hasil

   '0x',"1'5','3','0f'(128$#)"{~2^i.7
0x55555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555
0x33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
0x00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff
0x0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff
0x00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff
0x0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff
0x00000000000000000000000000000000ffffffffffffffffffffffffffffffff00000000000000000000000000000000ffffffffffffffffffffffffffffffff
0x0000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

Untuk jawaban ini, saya membutuhkan (idealnya) kata kerja dengan peringkat 0 1sehingga dapat menggunakannya dalam u"vdefinisi peringkat; Namun, mil mengamati bahwa 0 _itu cukup untuk tugas yang dihadapi.

┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│= │< │<.│<:│> │>.│>:│+ │+.│+:│* │*.│*:│_ 0 0│_ 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│
├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│- │-.│-:│% │%.│%:│^ │^.│$ │$.│$:│~.│~:│0 0 0│0 _ _│0 _ _│0 0 0│2 _ 2│0 0 0│0 0 0│0 0 0│_ 1 _│_ _ _│_ _ _│_ 0 0│_ 0 0│
├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│| │|.│, │,.│,:│; │;:│# │#.│#:│! │/:│\:│0 0 0│_ 1 _│_ _ _│_ _ _│_ _ _│_ _ _│1 _ _│_ 1 _│1 1 1│_ 1 0│0 0 0│_ _ _│_ _ _│
├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│[ │[:│] │{ │{.│{:│}.│}:│".│":│? │?.│a │_ _ _│_ _ _│_ _ _│1 0 _│_ 1 _│_ 0 0│_ 1 _│_ 0 0│1 _ _│_ 1 _│0 0 0│_ 0 0│_ _ _│
├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│A │A.│b │C │C.│d │D │e │e.│E │E.│f │H │_ _ _│1 0 _│_ _ _│_ _ _│1 1 _│_ _ _│_ _ _│_ _ _│_ _ _│_ _ _│0 _ _│_ _ _│_ _ _│
├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│i │i.│i:│I │I.│j │j.│L │L.│M │o │o.│p │_ _ _│1 _ _│0 _ _│_ _ _│1 _ _│_ _ _│0 0 0│_ _ _│_ 0 0│_ _ _│_ _ _│0 0 0│_ _ _│
├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│p.│p:│q │q:│r │r.│s │s:│S │t │T │u:│x:│1 1 0│0 _ _│_ _ _│0 0 0│_ _ _│0 0 0│_ _ _│_ _ _│_ _ _│_ _ _│_ _ _│_ _ _│_ _ _│
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

Di sini Anda melihat sekelompok representasi string kata kerja dengan peringkatnya masing-masing. Ini adalah skrip yang saya gunakan untuk menghasilkannya.

Conor O'Brien
sumber
Kata kerja dengan peringkat 0 _baik-baik saja di sini. Anda dapat mempersingkatnya menjadi 34 byte dengan'0x',"1'5','3','0f'(128$#)"{~2^i.7
miles
@miles Huh. Saya pikir saya sudah mencoba itu ... keren! dan saya lupa tentang fitur pengisian baris otomatis J, terima kasih lagi!
Conor O'Brien
4

Sebenarnya , 25 byte

9r`╙╙u9╙╙\#"0x%0128x"%`Mi

Cobalah online!

Solusi ini menggunakan fakta bahwa f(n) = 2**512//(2**2**n + 1)(di mana //pembagian lantai) untuk menyesuaikan nilai.

Penjelasan:

9r`╙╙u9╙╙\#"0x%0128x"%`Mi
9r`╙╙u9╙╙\#"0x%0128x"%`M   for n in range(1, 10):
      9╙╙\                   2**2**9//
   ╙╙u                                (2**2**n + 1)
          #"0x%0128x"%       pad with zeroes to 128 digits, prefix with "0x"
                        i  flatten and implicitly print
Mego
sumber
4

JavaScript (Firefox 30+), 139 113 112 92 83 80 byte

_=>[for(x of"970123456")(f=y=>y--?f(y)+(x>6?x-4:y>>x&1&&'f'):'0x')(128)].join`
`

Akhirnya tekan sweet spot rekursif :-) Menggunakan pemahaman string berguna-keren untuk menghemat 3 byte lebih .map:

_=>[..."970123456"].map(x=>(f=y=>y--?f(y)+(x>6?x-4:y>>x&1&&'f'):'0x')(128)).join`
`

.replace juga 83 byte:

_=>"970123456".replace(/./g,x=>(f=y=>y--?f(y)+(x>6?x-4:y>>x&1&&'f'):'0x')(128)+`
`)

Jika baris baru terkemuka diizinkan, ini juga akan menjadi 80 byte:

_=>"970123456".replace(/./g,x=>(f=y=>y--?f(y)+(x>6?x-4:y>>x&1&&'f'):`
0x`)(128))
Produksi ETH
sumber
3

Python 2 , 60 byte

k=1
exec"print'0x%0128x'%int(256/k*('0'*k+'1'*k),2);k*=2;"*9

Cobalah online!

Dennis
sumber
3

Bubblegum, 65 bytes

00000000: c5cb 4501 0441 1043 d17b d4fc 254b d110  ..E..A.C.{..%K..
00000010: f7cb 9761 9e7a 8d45 e451 4ce4 564c 04d7  ...a.z.E.QL.VL..
00000020: 2e11 b02b 8f08 80df aa5e 11fe fc77 762c  ...+.....^...wv,
00000030: 428b 5b8e ae8b 30c1 13b6 ce8b b091 377a  B.[...0.......7z
00000040: 01                                       .

Obligatory Bubblegum answer.

LegionMammal978
sumber
3

Haskell, 84 72 bytes

Porting @orlp's answer:

import Text.Printf
mapM(\n->printf"0x%0128x\n"$div(2^2^9)$2^2^n+1)[0..8]

94 byte alternatives without the power of Text.Printf:

import Data.List
mapM(putStrLn.("0x"++))$transpose$("53"++).reverse<$>sequence(["0f"]<*[1..7])

r=[0..127]
mapM(putStrLn.("0x"++))$('5'<$r):('3'<$r):[["0f"!!mod(div x(2^y))2|x<-r]|y<-[0..6]]
Angs
sumber
@nimi whoops, must have had loaded Control.Monad in the REPL. Fixed.
Angs
3

PowerShell v2+, 68 bytes

5,3|%{"0x"+"$_"*128}
($a=1)..7|%{"0x"+('0'*$a+'f'*$a)*(128/($a*=2))}

PowerShell doesn't have arbitrary precision integers without using [bigint] calls, and those can't be easily converted to hexadecimal, so we're instead treating this as a string-based challenge.

The first line handles the repeating 5 and 3 by just doing a string multiplication out to 128 characters and tacking a 0x on the front.

The next line loops from $a=1 to 7, each iteration outputting another string. Again we have the 0x tacked onto the front, and we're doing string multiplication in the middle to construct the appropriate number of 0 and f concatenated together, and then doing string multiplication of that out to the appropriate number of characters. Note we're using variable $a here, and not the loop counter $_, so we can properly scale (otherwise we'd need to loop like 1,2,4,8,16,32,64|%{...}, which is longer).

The resulting strings are left on the pipeline, and output via implicit Write-Output happens at program completion, with a newline between elements.

AdmBorkBork
sumber
3

V, 43 bytes

64i0fòYpÓ¨¨0«©¨f«©©û2}/²²³³òdd{3ÄÒ5jÒ3Îi0x

Try it online!

This uses one of the longest compressed regexes I've ever needed in a V answer. Here is the more readable version, where I added a byte for readable regexes, and changed the unprintable escape character to <esc>

64i0f<esc>òYpÓö((0+)(f+)){2}/²²³³òdd{3ÄÒ5jÒ3Îi0x

Explanation (using the readable version):

64i0f<esc>                                          " Insert 64 "0f"s and escape to normal mode
          ò                      ò                  " Recursively:
           Yp                                       "   Duplicate this line
             Ó                                      "   Substitute:
              ö                                     "     (Optionally Turn the readable version on)
               ((0+)(f+))                           "     One or more '0's followed by one or more 'f's
                         {2}                        "     Repeated twice
                            /                       "   With:
                             ²²                     "     The second capture group twice (the '0's)
                               ³³                   "     Followed by the third capture group twice (the 'f's)
                                                    "   Once the search is not found, the loop will break
                                  dd                " Delete a line (because we have one too many)
                                    {               " Move to the first line
                                     3Ä             " Make three copies of this line
                                       Ò5           " Replace the first one with '5's
                                         jÒ3        " Move down a line and replace the second with '3's
                                            Î       " On every line:
                                             i0x    "   Insert a '0x'
DJMcMayhem
sumber
3

JavaScript (ES6), 74 72 70 bytes

Includes the optional trailing newline.

f=(i=1152)=>i--?f(i)+(i&127?'':`
0x`)+('53'[y=i>>7]||i&1<<y-2&&'f'):''

Arnauld
sumber
2

Pyth - 31 30 bytes

To get pattern except for the 3's and 5's it cumulative reduces, each time doubling the chunks.

jm+"0x".[dd128+`3+`5.u.iNN6"0f

Try it online here.

Maltysen
sumber
2

Batch, 216 bytes

@echo off
set s=5
call:c
set s=3
call:c
set a=0
set b=f
for /l %%i in (1,1,7)do call:l %%i
exit/b
:l
set s=%a%%b%
:c
for /l %%j in (0%1,1,6)do call set s=%%s%%%%s%%
echo 0x%s%
set a=%a%%a%
set b=%b%%b%
Neil
sumber
2

Vim 72 bytes

i0x128a5Ypll128r3o0x64a0fa0Ypqqffdt0fft0p@qq@qqwYp@qq@w@w@w@w:%s/0$

TryItOnline!

Unprintables:

i0x^[128a5^[Ypll128r3o0x^[64a0f^[a0^[Ypqqffdt0fft0p@qq@qqwYp@qq@w@w@w@w:%s/0$

4 @ws pada akhirnya mengganggu saya, tetapi karena saya mengandalkan @qgagal pada akhir baris, gagal juga @ w. Saya mungkin mencoba menjalankan q 32 kali dan melihat apakah itu mengacaukan baris kemudian.

nmjcman101
sumber
2

C, 146 byte

#define F for(i=0;++i<129;)s[i+1]=
#define P ;puts(s);
i,j;f(){char s[131]={'0','x'};F'5'P F'3'P for(j=1;(j*=2)<129;){F(i-1)%j<j/2?'0':'f'P}}

Tidak Disatukan:

#define F for(i=0;++i<129;)s[i+1]=
#define P ;puts(s);
i,j;f(){
  char s[131]={'0','x'};
  F'5'P
  F'3'P
  for(j=1;(j*=2)<129;){
    F(i-1)%j<j/2?'0':'f'P 
  }
}
Karl Napf
sumber
133 bytes
ceilingcat
2

brainfuck , 211 byte

+++++++>++>>-[>>>>+<<++<+<-----]>--->>++++++++++>++<<<<<<[->----[>+++<--]>-->.<.++++++++[->>>>.<<<<]>>>.>--[<]<<]+<[->>----[>+++<--]>-->.<.++++++++[<<[>+>->.<<<-]>[<+>>->>.<<<-]>]>>>.<<<<[-<+>]<[->++<]>[-<+>]<<]

Cobalah online!

ბიმო
sumber
1
197 byte melalui beberapa pemeriksaan loop yang berbeda. Saya cukup yakin xgenerator dapat dipindahkan di luar loop sekarang
Jo King
2

Ruby , 66 60 45 byte

x=2;9.times{puts"0x%0128x"%(2**512/-~x);x*=x}

Cobalah online!

Ide dicuri dari orlp

GB
sumber
1

C#, 168 bytes

()={string R="",o="0",f="f";for(int i=0,j;i<9;i++){R+="0x";if(i>2){o+=o;f+=f;}for(j=0;j<128;){R+=i<1?"5":i<2?"3":o+f;j+=i>1?(int)Math.Pow(2,i-1):1;}R+="\n";}return R;};
Yodle
sumber
1

Stax, 19 bytes

⌡hÅék╝94"ºé♪╛#V┐5í╒

Run and debug it

Unpacked, ungolfed, and commented, it looks like this.

512r        [0..511]
{:Brm       convert each to bits and reverse each
M           transpose matrix, filling missing elements in rectangle with zero
m           map over each element of array, using the rest of the program.  outputs implicitly.
  4/        split bits into groups of 4
  {:b|Hm    convert each 4-bit binary number to single digit hex string
  .0xp      print "0x" without newline

Run this one

recursive
sumber
1

///, 193 bytes

/*/\/\///X/
0x*F/5555*G/FFFF*T/3333*U/TTTT*o/0f0f*1/oooo*t/00ff*2/tttt*g/0000*h/ffff*4/ghgh*6/gghh*7/gggg*8/hhhh*9/7788/0xGGGGGGGGXUUUUUUUUX11111111X22222222X44444444X66666666X78787878X99X77988

Try it online!

Erik the Outgolfer
sumber