Найти число лидирующих нулей в 64-разрядном целом числе

18

Проблема:

Найти число лидирующих нулей в 64-разрядном целом числе со знаком

Правила:

  • Ввод не может рассматриваться как строка; это может быть что угодно, где математические и побитовые операции управляют алгоритмом
  • Вывод должен быть проверен на соответствие 64-битному целому числу со знаком, независимо от языка
  • Применяются правила игры в гольф по умолчанию
  • Самый короткий код в байтах выигрывает

Тестовые случаи:

Эти тесты предполагают два дополненных числа со знаком. Если в вашем языке / решении отсутствует или используется другое представление целых чисел со знаком, сообщите об этом и предоставьте дополнительные тестовые примеры, которые могут иметь отношение к делу. Я включил несколько тестов, которые касаются двойной точности, но, пожалуйста, не стесняйтесь предлагать любые другие, которые должны быть перечислены.

input                output   64-bit binary representation of input (2's complement)
-1                   0        1111111111111111111111111111111111111111111111111111111111111111
-9223372036854775808 0        1000000000000000000000000000000000000000000000000000000000000000
9223372036854775807  1        0111111111111111111111111111111111111111111111111111111111111111
4611686018427387903  2        0011111111111111111111111111111111111111111111111111111111111111
1224979098644774911  3        0001000011111111111111111111111111111111111111111111111111111111
9007199254740992     10       0000000000100000000000000000000000000000000000000000000000000000
4503599627370496     11       0000000000010000000000000000000000000000000000000000000000000000
4503599627370495     12       0000000000001111111111111111111111111111111111111111111111111111
2147483648           32       0000000000000000000000000000000010000000000000000000000000000000
2147483647           33       0000000000000000000000000000000001111111111111111111111111111111
2                    62       0000000000000000000000000000000000000000000000000000000000000010
1                    63       0000000000000000000000000000000000000000000000000000000000000001
0                    64       0000000000000000000000000000000000000000000000000000000000000000
code-golf math restricted-source binary bitwise Дейв
источник
13
Добро пожаловать в PPCG! В чем причина «вход не может быть обработан как строка» ? Это дисквалифицирует все языки, которые не могут обрабатывать 64-битные целые числа, и вряд ли приведет к большему количеству ответов, которые принимают целое число, потому что это простой способ, если он доступен в любом случае.
Арно
1
Можем ли мы вернуться Falseвместо 0?
Джо Кинг,
4
@Arnauld Здесь и на других сайтах уже есть похожие вопросы, которые специально требуют строковых решений, но нет вопросов, которые открывают вопрос для математики и логических операций. Я надеюсь увидеть кучу разных подходов к этой проблеме, которые еще нигде не нашли ответа. Должно ли это быть открыто для струнных решений, чтобы быть всеобъемлющим?
Дейв
4
Некоторые процессоры, включая x86 и ARM, имеют специальные инструкции для этого (на самом деле x86 имеет несколько). Я всегда удивлялся, почему языки программирования не предоставляют эту возможность, поскольку в большинстве языков программирования сегодня нельзя вызывать инструкции по сборке.
Slebetman
1
@ user202729 Я думаю, что я сформулировал это плохо: «Вывод должен быть проверен на соответствие 64-битному целочисленному представлению числа независимо от языка». Под этим я подразумеваю, что этот вопрос определяет число нулей как число нулей в 64-разрядном целом числе со знаком. Я предполагаю, что сделал это ограничение для исключения целых чисел со знаком и без знака.
Дейв

Ответы:

41

машинный язык x86_64 в Linux, 6 байт

0:       f3 48 0f bd c7          lzcnt  %rdi,%rax
5:       c3                      ret

Требуется процессор Haswell или K10 или выше с lzcntинструкцией.

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

ceilingcat
источник
20
Строители снова бьют / с
Логерн
1
Я рекомендую указать используемое соглашение о вызовах (хотя вы и говорили о Linux)
qwr
@qwr Это похоже на соглашение о вызовах SysV, потому что параметр передается в% rdi и возвращается в% rax.
Логерн
24

Гексагония , 78 70 байт

2"1"\.}/{}A=<\?>(<$\*}[_(A\".{}."&.'\&=/.."!=\2'%<..(@.>._.\=\{}:"<><$

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

Разве этот вызов не слишком тривиален для практического языка? ;)

длина стороны 6. Я не могу вписать это в длину стороны 5 шестиугольников.

объяснение

user202729
источник
3
Я очень сильно смеялся над «объяснением». : D
Эрик Думинил
1
Я думаю, что у вас может быть слишком сложная обработка отрицательных чисел / ноль. Мне удалось подогнать аналогичную программу к длине стороны 5, не выполнив этого здоровенного вычисления 2 ^ 64. Хотя это явно не очень хорошо для игры в гольф!
FryAmTheEggman
@fry Ах да, отрицательные числа всегда имеют 0 ведущих нулей ... что определенно приводит к более короткой программе, потому что генерирует 2 ^ 64 долго.
user202729
12

Python , 31 байт

lambda n:67-len(bin(-n))&~n>>64

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

Экспрессон является побитовым &из двух частей:

67-len(bin(-n)) & ~n>>64

Это 67-len(bin(-n))дает правильный ответ для неотрицательных входных данных. Он берет длину в битах и ​​вычитает из 67, что на 3 больше, чем 64, чтобы компенсировать -0bпрефикс. Отрицание - это трюк, который нужно приспособить для n==0использования того, что отрицание не производит -знак впереди.

& ~n>>64Делает ответ вместо этого 0для негатива n. Когда n<0, ~n>>64равно 0 (на 64-битных целых числах), то и с ним дает 0. Когда n>=0, ~n>>64оценивает -1, и выполнение не &-1имеет никакого эффекта.

Python 2 , 36 байт

f=lambda n:n>0and~-f(n/2)or(n==0)*64

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

Арифметическая альтернатива.

XNOR
источник
9

Ява 8, 32 26 байт.

Long::numberOfLeadingZeros

Встроенные FTW.

-6 байт благодаря Кевину Круйссену

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

lukeg
источник
Ах, совсем забыл о numberOfLeadingZeros.. Вы можете n->n.numberOfLeadingZeros(n)
играть в
2
На самом деле, Long::numberOfLeadingZerosеще короче (26 байт).
Кевин Круйссен
6
Вау, это не очень часто бывает, что Java побеждает Python. Congrats!
Эрик Думинил
9

C (gcc) , 14 байтов

__builtin_clzl

Отлично работает на тио

C (gcc) , 35 29 байт

f(long n){n=n<0?0:f(n-~n)+1;}

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

Чем Деннис за 6 байтов

Флаги компилятора C (gcc) , 29 байт, Дэвид Фёрстер

-Df(n)=n?__builtin_clzl(n):64

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

l4m2
источник
3
Стоит отметить, что это только для 64-битных машин (или любых других с LP64 / ILP64 / и т. Д. ABI)
Руслан
1
Боже, это даже короче, чем любое использование встроенного GCC,__builtin_clzl с которым я могу придумать .
Дэвид Фёрстер
@Ruslan: хороший момент, в системах, где long32- битная версия (включая Windows x64), вам нужна __builtin_clzll(unsigned long long). godbolt.org/z/MACCKf . (В отличие от встроенных функций Intel, встроенные функции GNU C поддерживаются независимо от того, какую операцию можно выполнить с одной машинной инструкцией. В 32-разрядной версии x86 clzll компилируется в ветвь или cmov, чтобы выполнить lzcnt(low half)+32или lzcnt(high half). Или, bsrесли lzcntне доступно.
Питер Кордес,
Тестовые случаи включают «0», но __builtin_clz(l)(l)неопределенное поведение для нуля: «Если х равен 0, результат не определен».
MCCCS
1
@ MCCCS Если это работает, это считается. Вот почему я храню последний ответ
l4m2
6

Perl 6 , 35 28 26 байт

-2 байта благодаря nwellnhof

{to .fmt("%064b")~~/^0*/:}

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

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

Объяснение:

{                        }  # Anonymous code block
    .fmt("%064b")           # Format as a binary string with 64 digits
                 ~~         # Smartmatch against
                   /^0*/    # A regex counting leading zeroes
 to                     :   # Return the index of the end of the match
Джо Кинг
источник
6

JavaScript (Node.js) , 25 байт

Принимает входные данные как литерал BigInt.

f=x=>x<0?0:x?f(x/2n)-1:64

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

0

Arnauld
источник
Не будет n=>n<1?0:n.toString(2)-64выполнять то же самое?
Исмаэль Мигель
@IsmaelMiguel Полагаю, вы имели в виду n=>n<1?0:n.toString(2).length-64, но это не сработало бы в любом случае. Это было бы , я думаю.
Арно
1
@IsmaelMiguel Не беспокойся. :) .toString()Подход действительно работает, но нам все еще нужен литерал BigInt в качестве входных данных. В противном случае у нас есть только 52 бита мантиссы, что приводит к неверным результатам, когда точность теряется .
Арно
1
Тот факт, что суффикс BigInt совпадает с вашим параметром, очень запутан ...
Нейл
1
@Neil Неразборчивый код на PPCG ?? Этого не может быть! Исправлена! : p
Арнаулд
5

J , 18 байт

0{[:I.1,~(64$2)#:]

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

J , 19 байт

1#.[:*/\0=(64$2)#:]

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

Объяснение:

                #:  - convert 
                  ] - the input to
          (64$2)    - 64 binary digits
         =          - check if each digit equals 
        0           - zero
   [:*/\            - find the running product
1#.                 - sum
Гален Иванов
источник
1
1#.[:*/\1-_64{.#:(17) близко, но не работает для отрицательных чисел :(
Конор О'Брайен
@ Конор О'Брайен Хороший подход тоже!
Гален Иванов
4

05AB1E , 10 9 байтов

·bg65αsd*

I / O оба целые

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

·         # Double the (implicit) input
          #  i.e. -1 → -2
          #  i.e. 4503599627370496 → 9007199254740992
 b        # Convert it to binary
          #  i.e. -2 → "ÿ0"
          #  i.e. 9007199254740992 → 100000000000000000000000000000000000000000000000000000
  g       # Take its length
          #  i.e. "ÿ0" → 2
          #  i.e. 100000000000000000000000000000000000000000000000000000 → 54
   65α    # Take the absolute different with 65
          #  i.e. 65 and 2 → 63
          #  i.e. 65 and 54 → 11
      s   # Swap to take the (implicit) input again
       d  # Check if it's non-negative (>= 0): 0 if negative; 1 if 0 or positive
          #  i.e. -1 → 0
          #  i.e. 4503599627370496 → 1
        * # Multiply them (and output implicitly)
          #  i.e. 63 and 0 → 0
          #  i.e. 11 and 1 → 11
Кевин Круйссен
источник
4

Haskell , 56 байт

Спасибо xnor за обнаружение ошибки!

f n|n<0=0|1>0=sum.fst.span(>0)$mapM(pure[1,0])[1..64]!!n

Выделите достаточно памяти, попробуйте онлайн!

Может быть, вы хотите проверить это с меньшей константой: попробуйте 8-бит!

объяснение

mapM(pure[0,1])[1..64]mapM(pure[1,0])[1..64]{0,1}641sum.fst.span(>0)

ბიმო
источник
3

Powershell, 51 байт

param([long]$n)for(;$n-shl$i++-gt0){}($i,65)[!$n]-1

Тестовый скрипт:

$f = {

param([long]$n)for(;$n-shl$i++-gt0){}($i,65)[!$n]-1

}

@(
    ,(-1                   ,0 )
    ,(-9223372036854775808 ,0 )
    ,(9223372036854775807  ,1 )
    ,(4611686018427387903  ,2 )
    ,(1224979098644774911  ,3 )
    ,(9007199254740992     ,10)
    ,(4503599627370496     ,11)
    ,(4503599627370495     ,12)
    ,(2147483648           ,32)
    ,(2147483647           ,33)
    ,(2                    ,62)
    ,(1                    ,63)
    ,(0                    ,64)
) | % {
    $n,$expected = $_
    $result = &$f $n
    "$($result-eq$expected): $result"
}

Выход:

True: 0
True: 0
True: 1
True: 2
True: 3
True: 10
True: 11
True: 12
True: 32
True: 33
True: 62
True: 63
True: 64
Mazzy
источник
3

Java 8, 38 байт

int f(long n){return n<0?0:f(n-~n)+1;}

Ввести как long(64-разрядное целое), вывести как int(32-разрядное целое).

Порт ответа @ l4m2 C (gcc) .

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

Объяснение:

 int f(long n){       // Recursive method with long parameter and integer return-type
   return n<0?        //  If the input is negative:
           0          //   Return 0
          :           //  Else:
           f(n-~n)    //   Do a recursive call with n+n+1
                  +1  //   And add 1

РЕДАКТИРОВАТЬ: может быть 26 байтов с помощью встроенного, Long::numberOfLeadingZerosкак показано в ответе @lukeg Java 8 .

Кевин Круйссен
источник
3

APL + WIN, 34 байта

+/×\0=(0>n),(63⍴2)⊤((2*63)××n)+n←⎕

Объяснение:

n←⎕ Prompts for input of number as integer

((2*63)××n) If n is negative add 2 to power 63

(63⍴2)⊤ Convert to 63 bit binary

(0>n), Concatinate 1 to front of binary vector if n negative, 0 if positive

+/×\0= Identify zeros, isolate first contiguous group and sum if first element is zero
Грэхем
источник
3

C # (интерактивный компилятор Visual C #) , 42 байта

x=>x!=0?64-Convert.ToString(x,2).Length:64

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

C # (интерактивный компилятор Visual C #) , 31 байт

int c(long x)=>x<0?0:c(x-~x)+1;

Еще короче, основываясь на ответе C (gcc) @ l4m2. Никогда не знал, что можно объявить такие функции, спасибо @Dana!

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

Воплощение невежества
источник
1
Я думаю, что это действительно? tio.run/##ZZA/...
Dana
3

Желе ,  10  9 байт

-1 благодаря изящному трюку Эрика Аутгольфера (теперь он неотрицателен AƑ)

ḤBL65_×AƑ

Монадическая ссылка, принимающая целое число (в пределах диапазона), которое дает целое число.

Попробуйте онлайн! Или посмотрите набор тестов .

10 было ḤBL65_ɓ>-×

Вот еще одно 10-байтовое решение, которое мне нравится, так как оно говорит, что это «BOSS» ...

BoṠS»-~%65

Тест-сьют здесь

... BoṠS63r0¤i, BoṠS63ŻṚ¤iили BoṠS64ḶṚ¤iбудет также работать.

Еще 10 байтов (от Дениса) есть æ»64ḶṚ¤Äċ0(опять æ»63r0¤Äċ0и æ»63ŻṚ¤Äċ0тоже будет работать)

Джонатан Аллан
источник
9 байтов
Эрик Outgolfer
@EriktheOutgolfer Я подумал про себя: «Должен быть способ игры в гольф умножением на isNonNegative» и вообще не думал о Ƒбыстрой, очень хорошей работе!
Джонатан Аллан
1
На самом деле, я теоретизировал AƑуже довольно давно . Имейте в виду, что это не векторизация! ;-) Это на самом деле "сгладить, а затем проверить, все ли элементы неотрицательны".
Эрик Outgolfer
2

Perl 5 , 37 байт

sub{sprintf("%064b",@_)=~/^0*/;$+[0]}

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

Или это 46 байтов, если «stringification» не допускается: sub z

sub{my$i=0;$_[0]>>64-$_?last:$i++for 1..64;$i}
Кжетил С.
источник
s/length$&/$+[0]/(-3 байта);)
Дада
IMO, вы не можете удалить subключевое слово из ответов, содержащих функции Perl 5.
nwellnhof
Я видел что-то похожее на удаление subв ответах для других языков, perl6, powershell и других.
Кжетил С.
В Perl6, я думаю, вам не нужно sub{}создавать подпункт (аноним?), Который объясняет, почему он опущен в ответах Perl6. Я согласен с @nwellnhof, что вам нельзя разрешать удалять sub. (когда я был еще активен, как год назад или около того, это было правилом)
Дада
изменилось сейчас. И в комплекте $+[0].
Кжетил С.
2

Swift (на 64-битной платформе), 41 байт

Объявляет вызванное замыкание, fкоторое принимает и возвращает Int. Это решение работает только правильно 64-разрядные платформы, где Intнаходится typealiasЭда Int64. (На 32-битной платформе Int64может использоваться явно для типа параметра замыкания, добавляя 2 байта.)

let f:(Int)->Int={$0.leadingZeroBitCount}

В Swift даже основной целочисленный тип является обычным объектом, объявленным в стандартной библиотеке. Это средство Intможет иметь методы и свойства, такие как leadingZeroBitCount(что требуется для всех типов, соответствующих FixedWidthIntegerпротоколу стандартной библиотеки ).

NobodyNada - Восстановить Монику
источник
интересный. напоминает мне о ржавчине. я думаю, что это должно считаться 20 байтов, .leadingZeroBitCount
не
2

Haskell , 24 байта

f n|n<0=0
f n=1+f(2*n+1)

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

По сути, это то же самое, что и Java-решение Кевина Круйссена, но я нашел его независимо.

Аргумент должен иметь тип Intдля 64-битной сборки или Int64для чего угодно.

объяснение

Если аргумент отрицательный, результат сразу равен 0. В противном случае мы сдвигаемся влево, заполняя единицы , пока не достигнем отрицательного числа. Это заполнение позволяет нам избежать специального случая для 0.

Просто для справки, вот очевидный / эффективный способ:

34 байта

import Data.Bits
countLeadingZeros
dfeuer
источник
1

Perl 5 -p , 42 байта

1while$_>0&&2**++$a-1<$_;$_=0|$_>=0&&64-$a

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

Больше, чем решение на основе цепочек, но достойное математическое решение.

Xcali
источник
Действительно не работает, если я не ошибаюсь
Дада
@ Дада Я вижу, что есть несколько случаев, когда деление с плавающей запятой не совсем правильно работает. Я вставил intзвонок, который должен решить проблему.
Xcali
Извините, я потерпел неудачу с моим копированием, это может показаться. Это то, что я хотел отправить;)
Дада
1

APL (NARS), 15 символов, 30 байтов

{¯1+1⍳⍨⍵⊤⍨64⍴2}

проверить несколько номеров, чтобы увидеть, как использовать:

  f←{¯1+1⍳⍨⍵⊤⍨64⍴2}
  f ¯9223372036854775808
0
  f 9223372036854775807
1
RosLuP
источник
1

K (нгн / к) , 6 байтов

64-#2\

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

2\ закодировать аргумент в двоичном

# длина

64- вычесть из 64

СПП
источник
# = length... выглядит на основе строки
Тит
2
@Titus 2\ дает список целых чисел и #находит его длину. здесь не задействованы никакие строки.
нгн
1

PHP, 50 46 байт

for(;0<$n=&$argn;$n>>=1)$i++;echo$n<0?0:64-$i;

Запустите как трубу -Rили попробуйте онлайн ,

<?=$argn<0?0:0|64-log($argn+1,2);имеет проблемы с округлением; так что я прошел долгий путь.

Titus
источник
1

Wolfram Language (Mathematica) , 41 байт

Формула для положительных чисел просто 63-Floor@Log2@#&. Правила замены используются для особых случаев нулевого и отрицательного ввода.

Входные данные не должны быть 64-разрядным целым числом со знаком. Это эффективно займет слово ввода, чтобы превратить его в целое число. Если вы введете число вне нормальных границ для 64-разрядного целого числа, оно сообщит, что возвращает отрицательное число, указывающее, сколько еще битов потребуется для хранения этого целого числа.

63-Floor@Log2[#/.{_?(#<0&):>2^63,0:>.5}]&

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

Решение @ LegionMammal978 немного короче - 28 байтов. Ввод должен быть целым числом. Согласно документации: « BitLength[n]эффективно эффективная версия Floor[Log[2,n]]+1». Он автоматически обрабатывает случай, когда 0вместо отчета правильно сообщается ноль -∞.

Wolfram Language (Mathematica) , 28 байт

Boole[#>=0](64-BitLength@#)&

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

Келли Лоудер
источник
1
Boole[#>=0](64-BitLength@#)&немного короче на 28 байтов. Он использует ту же основную концепцию, что и ваша, но применяется BitLengthи Boole.
LegionMammal978
Я полностью забыл о BitLength!
Келли Лоудер
1

bitNumber - math.ceil (math.log (number) / math.log (2))

например, 64-битный NUMBER: 9223372036854775807 math.ceil (math.log (9223372036854775807) / math.log (2)) ANS: 63

user90293
источник
Если бы вы могли добавить к этому название языка, это было бы здорово, так как люди, скорее всего, проголосовали бы без ответов, в которых не указано название языка
Jono 2906