25
\$\begingroup\$

There’s a famous tricky algorithm for counting the number of set bits in a 32-bit unsigned integer:

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

I won’t explain it here. But imagine similar code for 512-bit integers! The hexadecimal constants would be huge, and form a pretty pattern. Your task is simply to print this exact output:

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

No trailing spaces, please — though a single trailing newline is optional.

This is , so the shortest answer (in bytes) wins.

\$\endgroup\$
  • \$\begingroup\$ Are we allowed to take input (as in something like 0x0x0x0x0x0x0x0x0x)? \$\endgroup\$ – ouflak Oct 31 at 14:26
  • \$\begingroup\$ @ouflak No. ——— \$\endgroup\$ – Lynn Oct 31 at 22:19

25 Answers 25

3
\$\begingroup\$

05AB1E, 26 22 21 bytes

05AB1E uses the CP-1252 encoding.

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

Try it online!

Explanation

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

Other versions that might be improved

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ÿ,
\$\endgroup\$
21
\$\begingroup\$

Python 2, 52 49 46 bytes

The kth number is given by 2**512/(2**2**k + 1). This is for a 512 bit number, so it's trivial to extend the pattern to different widths.

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

3 bytes saved thanks to Dennis.
3 bytes saved thanks to xnor.

\$\endgroup\$
  • 2
    \$\begingroup\$ The advantages of arbitrary-precision integers... \$\endgroup\$ – ETHproductions Dec 1 '16 at 2:34
  • \$\begingroup\$ Nice. This saves a few bytes. \$\endgroup\$ – Dennis Dec 1 '16 at 2:34
  • \$\begingroup\$ Shorter to keep squaring: l=2;exec"print'0x%0128x'%(2**512/-~l);l*=l;"*9 \$\endgroup\$ – xnor Dec 1 '16 at 5:51
  • 1
    \$\begingroup\$ It warms my heart to see Python in the vote-lead :) \$\endgroup\$ – Tobias Kienzler Dec 1 '16 at 7:17
  • 4
    \$\begingroup\$ @TuukkaX I just have a lot of experience with bit twiddling hacks. I used Wolfram Alpha a lot to simplify sums and such. But basically I made the pattern 01010101, 00010001, 00000001, and then multiplied those by 1, 11, 1111 to get the correct binary patterns. For example 01010101 you can get the formula for a certain width w by doing sum 2^(2*k) for k = 0, w/2 - 1 and finding out it's (2**w - 1)/3. \$\endgroup\$ – orlp Dec 1 '16 at 9:15
7
\$\begingroup\$

PHP, 111 110 108 bytes

One byte saved thanks to @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)));

What´s the pattern for 1024 bits? :D

\$\endgroup\$
  • 1
    \$\begingroup\$ You can save a byte by using $x<65 rather than $i++<7. This time I tested it and everything. \$\endgroup\$ – user59178 Dec 1 '16 at 9:42
6
\$\begingroup\$

Retina, 43 bytes

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

Try it online!

Explanation

This makes a lot of use of the generally underused : option which lets you print intermediate results, because it's a lot shorter to modify a single line than to build up the whole output.

:`
0x128$*5

This replaces the empty input with 0x followed by 128 5s and prints it to generate the first line.

:`5
3

This one replaces the 5s with 3s to generate the second line and prints it as well.

;{:`33
0f

This is the last special-cased line and it turns every two 3s into 0f to generate the third line. This also starts a loop through the last two stages ({). However, this stage won't do anything after the first iteration except print the current state. The ; suppresses the output at the very end of the program to avoid duplicating the last line.

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

This substitution now transforms each line into the next, by swapping every other pair of fs and 0s. The "every other pair" condition is enforced by matching a zero in front of the f, which makes it impossible to match consecutive pairs since matches cannot overlap.

\$\endgroup\$
6
\$\begingroup\$

Vim, 32 bytes

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

I only need to manually write the first 5 and 3, and the macro takes care of the rest, "doubling the bit count" each time it runs. The order of the steps in the macro is a bit weird (make a new f line, block-wise copy, reuse the visual block size to put 0s in the f line), but it's the fastest variant I've found.

\$\endgroup\$
5
\$\begingroup\$

Pyth, 26 bytes

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

Port of my Python answer.

\$\endgroup\$
5
\$\begingroup\$

J, 46 34 bytes

I'm working on golfing this, but this baby likes to stay at 46 bytes... Not anymore! -12 bytes thanks to miles!

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

Try it online! :D

Result

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

For this answer, I needed (ideally) a verb with rank 0 1 so as to use it in the u"v definition of rank; however, miles observed that 0 _ was sufficient for the task at hand.

┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│= │< │<.│<:│> │>.│>:│+ │+.│+:│* │*.│*:│_ 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│_ _ _│_ _ _│_ _ _│_ _ _│_ _ _│_ _ _│_ _ _│
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

Here you see a bunch of verbs' string representations with their respective ranks. This is the script I used to generate it.

\$\endgroup\$
  • \$\begingroup\$ A verb with rank 0 _ is fine here. You can shorten it to 34 bytes with '0x',"1'5','3','0f'(128$#)"{~2^i.7 \$\endgroup\$ – miles Dec 1 '16 at 11:25
  • \$\begingroup\$ @miles Huh. I thought I tried that... cool! and I forgot about J's auto-row-fill feature, thanks again! \$\endgroup\$ – Conor O'Brien Dec 1 '16 at 11:29
4
\$\begingroup\$

Actually, 25 bytes

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

Try it online!

This solution uses the fact that f(n) = 2**512//(2**2**n + 1) (where // is floored division) to compure the values.

Explanation:

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
\$\endgroup\$
4
\$\begingroup\$

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

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

Finally hit the recursive sweet spot :-) Uses a handy-dandy string comprehension to save 3 bytes over .map:

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

.replace is also 83 bytes:

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

If a leading newline were allowed, this would also be 80 bytes:

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

Python 2, 60 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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]]
\$\endgroup\$
  • \$\begingroup\$ @nimi whoops, must have had loaded Control.Monad in the REPL. Fixed. \$\endgroup\$ – Angs Dec 1 '16 at 6:50
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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'
\$\endgroup\$
3
\$\begingroup\$

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'):''

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

console.log(f())

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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%
\$\endgroup\$
2
\$\begingroup\$

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$

The 4 @ws at the end are bugging me, but because I was relying on the @q to fail out at the end of a line, it fails out the @w as well. I might try just running q 32 times and seeing if it messes up the later lines.

\$\endgroup\$
2
\$\begingroup\$

C, 146 bytes

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

Ungolfed:

#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 
  }
}
\$\endgroup\$
2
\$\begingroup\$

brainfuck, 211 bytes

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ 197 bytes through some different loop checks. I'm pretty sure the x generator can be moved outside the loop now \$\endgroup\$ – Jo King Mar 18 at 0:37
2
\$\begingroup\$

GNU sed 4.2.2, 77

s/^/0x5/
:
s/x5{,127}$/&5/
t
p
y/5/3/
p
s/33/0f/gp
:a
s/(f+)(0+f+)/\2\1/gp
ta

Try it online.

\$\endgroup\$
2
\$\begingroup\$

Ruby, 66 60 45 bytes

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

Try it online!

Idea stolen from orlp

\$\endgroup\$
1
\$\begingroup\$

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;};
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

///, 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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.