Волшебные номера попкорна

25

Есть известный хитрый алгоритм для подсчета количества установленных битов в 32-разрядном целом числе без знака:

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

Я не буду объяснять это здесь. Но представьте себе подобный код для 512-битных целых чисел! Шестнадцатеричные константы будут огромными и образуют симпатичный рисунок. Ваша задача просто напечатать этот точный вывод :

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

Нет пробелов, пожалуйста, - хотя один завершающий символ новой строки не является обязательным.

Это , поэтому выигрывает самый короткий ответ (в байтах).

Линн
источник
Разрешено ли принимать входные данные (например, 0x0x0x0x0x0x0x0x0x)?
ouflak
@ouflak Нет. ———
Линн

Ответы:

3

05AB1E , 26 22 21 байт

05AB1E использует кодировку CP-1252 .

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

Попробуйте онлайн!

объяснение

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

Другие версии, которые могут быть улучшены

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
источник
21

Python 2, 52 49 46 байт

K-е число задается как 2**512/(2**2**k + 1). Это для 512-битного числа, поэтому тривиально расширить шаблон до различной ширины.

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

3 байта сохранены благодаря Денису.
3 байта сохранены благодаря xnor.

orlp
источник
2
Преимущества целых чисел произвольной точности ...
ETHproductions
Ницца. Это экономит несколько байтов.
Деннис
Короче, чтобы держать в квадрате:l=2;exec"print'0x%0128x'%(2**512/-~l);l*=l;"*9
xnor
1
Это согревает мое сердце, когда я вижу, что Python в лидерах голосования :)
Тобиас Кинцлер
4
@TuukkaX У меня просто большой опыт работы с хулиганскими взломами. Я много использовал Wolfram Alpha для упрощения сумм и тому подобного. Но в основном я сделал рисунок 01010101, 00010001, 00000001, а затем умножаются на том 1, 11, 1111чтобы получить правильные бинарные шаблоны. Например, 01010101вы можете получить формулу для определенной ширины w, выполнив sum 2^(2*k) for k = 0, w/2 - 1и выяснив ее (2**w - 1)/3.
orlp
7

PHP, 111 110 108 байт

Один байт сохранен благодаря @ 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)));

Каков шаблон для 1024 бит? : D

Titus
источник
1
Вы можете сохранить байт, используя $x<65вместо $i++<7. На этот раз я проверил это и все.
user59178
6

Сетчатка , 43 байта

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

Попробуйте онлайн!

объяснение

Это широко использует обычно недоиспользуемую :опцию, которая позволяет печатать промежуточные результаты, потому что модифицировать одну строку намного короче, чем создавать весь вывод.

:`
0x128$*5

Это заменяет пустой ввод с 0xпоследующим 128 5с и печатает его для генерации первой строки.

:`5
3

Эта строка заменяет 5s на 3s, чтобы сгенерировать вторую строку, а также печатает ее.

;{:`33
0f

Это последняя строка в специальном регистре, и каждые две 3секунды она превращается 0fв третью строку. Это также запускает цикл через последние два этапа ( {). Однако этот этап ничего не сделает после первой итерации, кроме вывода текущего состояния. В ;подавляет выход в самом конце программы , чтобы избежать дублирования в последней строке.

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

Эта замена теперь преобразует каждую строку в следующую, заменяя каждую другую пару fs и 0s. Условие «каждая другая пара» обеспечивается путем сопоставления нуля перед символом f, что делает невозможным сопоставление последовательных пар, поскольку совпадения не могут перекрываться.

Мартин Эндер
источник
6

Vim, 32 байта

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

Мне нужно только вручную написать первое 5и 3, а макрос позаботится об остальном, «удваивая число битов» при каждом запуске. Порядок шагов в макросе немного странный (создать новую fстроку, блочную копию, повторно использовать размер визуального блока, чтобы поместить 0s в fстроку), но это самый быстрый вариант, который я нашел.

udioica
источник
5

Pyth, 26 байт

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

Порт моего Python ответа.

orlp
источник
5

J, 46 34 байта

Я работаю над игрой в гольф, но этот ребенок любит оставаться на 46 байтах ... Больше нет! -12 байт благодаря милям!

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

Попробуйте онлайн! : D

Результат

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

Для этого ответа мне нужен (в идеале) глагол с рангом, 0 1чтобы использовать его в u"vопределении ранга; Однако, миль заметил, что 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 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│_ _ _│_ _ _│_ _ _│_ _ _│_ _ _│_ _ _│_ _ _│
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

Здесь вы видите кучу строковых представлений глаголов с соответствующими им рангами. Это сценарий, который я использовал для его создания.

Конор О'Брайен
источник
Глагол с рангом 0 _хорошо здесь. Вы можете сократить его до 34 байтов с'0x',"1'5','3','0f'(128$#)"{~2^i.7
миль
@ Майлз Я думал, что попробовал это ... круто! и я забыл об автозаполнении J, еще раз спасибо!
Конор О'Брайен
4

На самом деле , 25 байтов

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

Попробуйте онлайн!

Это решение использует тот факт, что f(n) = 2**512//(2**2**n + 1)(где //находится этажное деление) для вычисления значений.

Объяснение:

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
источник
4

JavaScript (Firefox 30+), 139 113 112 92 83 80 байт

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

Наконец, попал в рекурсивную сладкую точку :-) Использует удобное понимание строки денди, чтобы сэкономить 3 байта .map:

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

.replace также 83 байта:

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

Если бы разрешен начальный символ новой строки, это также будет 80 байтов:

_=>"970123456".replace(/./g,x=>(f=y=>y--?f(y)+(x>6?x-4:y>>x&1&&'f'):`
0x`)(128))
ETHproductions
источник
3

Жевательная резинка , 65 байт

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                                       .

Обязательный Bubblegum ответ.

LegionMammal978
источник
3

Хаскелл, 84 72 байта

Портирование @ orlp ответ:

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

94 байта альтернативы без возможности 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
источник
@nimi whoops, должно быть, загружено Control.Monadв REPL. Исправлена.
Ангс
3

PowerShell v2 +, 68 байт

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

PowerShell не имеет произвольных целочисленных значений точности без использования [bigint] вызовов, и их нелегко преобразовать в шестнадцатеричное, поэтому вместо этого мы рассматриваем это как вызов на основе строк.

Первая строка обрабатывает повторение 5и 3просто умножает строку на 128символы и прикрепляет0x к передней части.

Следующая строка переходит из цикла $a=1в 7, каждая итерация выводит другую строку. Опять мы имеем 0xприкрепил на фронт, и мы делаем строковое умножение в середине построить соответствующее число 0и fсцепляются вместе, а затем делать строковое умножение этого отказа на соответствующее число символов. Обратите внимание, что здесь используется переменная $a, а не счетчик цикла $_, поэтому мы можем правильно масштабировать (в противном случае нам нужно было бы выполнить цикл как1,2,4,8,16,32,64|%{...} , что длиннее).

Результирующие строки остаются в конвейере, и вывод через неявный Write-Outputпроисходит при завершении программы, с новой строкой между элементами.

AdmBorkBork
источник
3

V , 43 байта

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

Попробуйте онлайн!

При этом используется одно из самых длинных сжатых регулярных выражений, которое мне когда-либо требовалось в ответе V. Вот более читаемая версия, где я добавил байт для читаемых регулярных выражений и изменил непечатный escape-символ на<esc>

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

Объяснение (используя читаемую версию):

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
источник
3

JavaScript (ES6), 74 72 70 байт

Включает дополнительный завершающий перевод строки.

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

Arnauld
источник
2

Пакет, 216 байт

@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%
Нил
источник
2

Vim 72 байта

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

TryItOnline!

непечатные:

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

4 @wв конце вызывают у меня проблемы, но, поскольку я рассчитывал, что @qв конце строки произойдет сбой, он также завершится ошибкой @w. Я мог бы попытаться просто запустить q 32 раза и посмотреть, не испортит ли это более поздние строки.

nmjcman101
источник
2

C, 146 байтов

#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 
  }
}
Карл Напф
источник
133 байта
floorcat
2

брейкфук , 211 байт

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

Попробуйте онлайн!

ბიმო
источник
1
197 байтов через несколько различных проверок цикла. Я почти уверен, что xгенератор теперь можно вывести из цикла
Джо Кинг,
1

C #, 168 байт

()={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
источник
1

Stax , 19 байт

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

Запустите и отладьте его

Распакованный, размазанный и прокомментированный, это выглядит так.

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

Запустите этот

рекурсивный
источник
1

/// , 193 байта

/*/\/\///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

Попробуйте онлайн!

Эрик Аутгольфер
источник