Find the number of leading zeroes in a 64-bit integer
Problem:
Find the number of leading zeroes in a 64-bit signed integer
Rules:
- The input cannot be treated as string; it can be anything where math and bitwise operations drive the algorithm
- The output should be validated against the 64-bit signed integer representation of the number, regardless of language
- Default code golf rules apply
- Shortest code in bytes wins
Test cases:
These tests assume two's complement signed integers. If your language/solution lacks or uses a different representation of signed integers, please call that out and provide additional test cases that may be relevant. I've included some test cases that address double precision, but please feel free to suggest any others that should be listed.
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
|
show 7 more comments
Problem:
Find the number of leading zeroes in a 64-bit signed integer
Rules:
- The input cannot be treated as string; it can be anything where math and bitwise operations drive the algorithm
- The output should be validated against the 64-bit signed integer representation of the number, regardless of language
- Default code golf rules apply
- Shortest code in bytes wins
Test cases:
These tests assume two's complement signed integers. If your language/solution lacks or uses a different representation of signed integers, please call that out and provide additional test cases that may be relevant. I've included some test cases that address double precision, but please feel free to suggest any others that should be listed.
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
11
Welcome to PPCG! What's the reason behind "the input cannot be treated as string"? This disqualifies all languages that can't handle 64-bit integers and is unlikely to lead to more answers that take an integer, because this is the straightforward way when available anyway.
– Arnauld
Dec 9 at 23:26
1
Can we returnFalse
instead of0
?
– Jo King
Dec 9 at 23:33
4
@Arnauld There are already similar questions here and on other sites that specifically call for string-based solutions, but nothing that opens the question to math and logical operations. My hope is to see a bunch of different approaches to this problem that are not already answered elsewhere. Should this be opened to string solutions as well to be all-inclusive?
– Dave
Dec 9 at 23:40
3
Several CPUs including x86 and ARM have specific instructions for this (x86 actually have several). I've always wondered why programming languages don't expose this feature since in most programming languages today you can't invoke assembly instructions.
– slebetman
Dec 10 at 5:43
1
@user202729 I think I worded this poorly: 'The output should be validated against the 64-bit signed integer representation of the number, regardless of language' What I mean by that is that this question defines the number of zeros as the number of zeros in a 64-bit signed integer. I guess I made that constraint to eliminate signed vs unsigned integers.
– Dave
Dec 11 at 0:26
|
show 7 more comments
Problem:
Find the number of leading zeroes in a 64-bit signed integer
Rules:
- The input cannot be treated as string; it can be anything where math and bitwise operations drive the algorithm
- The output should be validated against the 64-bit signed integer representation of the number, regardless of language
- Default code golf rules apply
- Shortest code in bytes wins
Test cases:
These tests assume two's complement signed integers. If your language/solution lacks or uses a different representation of signed integers, please call that out and provide additional test cases that may be relevant. I've included some test cases that address double precision, but please feel free to suggest any others that should be listed.
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
Problem:
Find the number of leading zeroes in a 64-bit signed integer
Rules:
- The input cannot be treated as string; it can be anything where math and bitwise operations drive the algorithm
- The output should be validated against the 64-bit signed integer representation of the number, regardless of language
- Default code golf rules apply
- Shortest code in bytes wins
Test cases:
These tests assume two's complement signed integers. If your language/solution lacks or uses a different representation of signed integers, please call that out and provide additional test cases that may be relevant. I've included some test cases that address double precision, but please feel free to suggest any others that should be listed.
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
code-golf math restricted-source binary bitwise
edited Dec 11 at 22:33
cat
4,30321939
4,30321939
asked Dec 9 at 23:08
Dave
10018
10018
11
Welcome to PPCG! What's the reason behind "the input cannot be treated as string"? This disqualifies all languages that can't handle 64-bit integers and is unlikely to lead to more answers that take an integer, because this is the straightforward way when available anyway.
– Arnauld
Dec 9 at 23:26
1
Can we returnFalse
instead of0
?
– Jo King
Dec 9 at 23:33
4
@Arnauld There are already similar questions here and on other sites that specifically call for string-based solutions, but nothing that opens the question to math and logical operations. My hope is to see a bunch of different approaches to this problem that are not already answered elsewhere. Should this be opened to string solutions as well to be all-inclusive?
– Dave
Dec 9 at 23:40
3
Several CPUs including x86 and ARM have specific instructions for this (x86 actually have several). I've always wondered why programming languages don't expose this feature since in most programming languages today you can't invoke assembly instructions.
– slebetman
Dec 10 at 5:43
1
@user202729 I think I worded this poorly: 'The output should be validated against the 64-bit signed integer representation of the number, regardless of language' What I mean by that is that this question defines the number of zeros as the number of zeros in a 64-bit signed integer. I guess I made that constraint to eliminate signed vs unsigned integers.
– Dave
Dec 11 at 0:26
|
show 7 more comments
11
Welcome to PPCG! What's the reason behind "the input cannot be treated as string"? This disqualifies all languages that can't handle 64-bit integers and is unlikely to lead to more answers that take an integer, because this is the straightforward way when available anyway.
– Arnauld
Dec 9 at 23:26
1
Can we returnFalse
instead of0
?
– Jo King
Dec 9 at 23:33
4
@Arnauld There are already similar questions here and on other sites that specifically call for string-based solutions, but nothing that opens the question to math and logical operations. My hope is to see a bunch of different approaches to this problem that are not already answered elsewhere. Should this be opened to string solutions as well to be all-inclusive?
– Dave
Dec 9 at 23:40
3
Several CPUs including x86 and ARM have specific instructions for this (x86 actually have several). I've always wondered why programming languages don't expose this feature since in most programming languages today you can't invoke assembly instructions.
– slebetman
Dec 10 at 5:43
1
@user202729 I think I worded this poorly: 'The output should be validated against the 64-bit signed integer representation of the number, regardless of language' What I mean by that is that this question defines the number of zeros as the number of zeros in a 64-bit signed integer. I guess I made that constraint to eliminate signed vs unsigned integers.
– Dave
Dec 11 at 0:26
11
11
Welcome to PPCG! What's the reason behind "the input cannot be treated as string"? This disqualifies all languages that can't handle 64-bit integers and is unlikely to lead to more answers that take an integer, because this is the straightforward way when available anyway.
– Arnauld
Dec 9 at 23:26
Welcome to PPCG! What's the reason behind "the input cannot be treated as string"? This disqualifies all languages that can't handle 64-bit integers and is unlikely to lead to more answers that take an integer, because this is the straightforward way when available anyway.
– Arnauld
Dec 9 at 23:26
1
1
Can we return
False
instead of 0
?– Jo King
Dec 9 at 23:33
Can we return
False
instead of 0
?– Jo King
Dec 9 at 23:33
4
4
@Arnauld There are already similar questions here and on other sites that specifically call for string-based solutions, but nothing that opens the question to math and logical operations. My hope is to see a bunch of different approaches to this problem that are not already answered elsewhere. Should this be opened to string solutions as well to be all-inclusive?
– Dave
Dec 9 at 23:40
@Arnauld There are already similar questions here and on other sites that specifically call for string-based solutions, but nothing that opens the question to math and logical operations. My hope is to see a bunch of different approaches to this problem that are not already answered elsewhere. Should this be opened to string solutions as well to be all-inclusive?
– Dave
Dec 9 at 23:40
3
3
Several CPUs including x86 and ARM have specific instructions for this (x86 actually have several). I've always wondered why programming languages don't expose this feature since in most programming languages today you can't invoke assembly instructions.
– slebetman
Dec 10 at 5:43
Several CPUs including x86 and ARM have specific instructions for this (x86 actually have several). I've always wondered why programming languages don't expose this feature since in most programming languages today you can't invoke assembly instructions.
– slebetman
Dec 10 at 5:43
1
1
@user202729 I think I worded this poorly: 'The output should be validated against the 64-bit signed integer representation of the number, regardless of language' What I mean by that is that this question defines the number of zeros as the number of zeros in a 64-bit signed integer. I guess I made that constraint to eliminate signed vs unsigned integers.
– Dave
Dec 11 at 0:26
@user202729 I think I worded this poorly: 'The output should be validated against the 64-bit signed integer representation of the number, regardless of language' What I mean by that is that this question defines the number of zeros as the number of zeros in a 64-bit signed integer. I guess I made that constraint to eliminate signed vs unsigned integers.
– Dave
Dec 11 at 0:26
|
show 7 more comments
29 Answers
29
active
oldest
votes
x86_64 machine language on Linux, 6 bytes
0: f3 48 0f bd c7 lzcnt %rdi,%rax
5: c3 ret
Requires Haswell or K10 or higher processor with lzcnt
instruction.
Try it online!
18
Builtins strike again /s
– Logern
Dec 10 at 2:06
1
I recommend specifying the calling convention used (though you did say on Linux)
– qwr
Dec 12 at 8:02
@qwr It looks like SysV calling convention because the parameter is passed in %rdi and it is returned in %rax.
– Logern
Dec 15 at 4:21
add a comment |
Hexagony, 78 70 bytes
2"1".}/{}A=<?>(<$*}[_(A".{}."&.'&=/.."!=2'%<..(@.>._.={}:"<><$
Try it online!
Isn't this challenge too trivial for a practical language? ;)
side length 6. I can't fit it in a side length 5 hexagon.
Explanation
3
I laughed really hard at the "explanation". :D
– Eric Duminil
Dec 10 at 18:45
1
I think you may have overcomplicated handling negative numbers/zero. I managed to fit a similar program into side length 5 by not doing that hefty 2^64 calculation. It clearly isn't well golfed yet, though!
– FryAmTheEggman
Dec 10 at 22:56
@fry Ah right, negative numbers always have 0 leading zeroes... which definitely leads to shorter program because generates 2^64 is long.
– user202729
Dec 11 at 5:39
add a comment |
Python, 31 bytes
lambda n:67-len(bin(-n))&~n>>64
Try it online!
The expresson is the bitwise &
of two parts:
67-len(bin(-n)) & ~n>>64
The 67-len(bin(-n))
gives the correct answer for non-negative inputs. It takes the bit length, and subtracts from 67, which is 3 more than 64 to compensate for the -0b
prefix. The negation is a trick to adjust for n==0
using that negating it doesn't produce a -
sign in front.
The & ~n>>64
makes the answer instead be 0
for negative n
. When n<0
, ~n>>64
equals 0 (on 64-bit integers), so and-ing with it gives 0
. When n>=0
, the ~n>>64
evaluates to -1
, and doing &-1
has no effect.
Python 2, 36 bytes
f=lambda n:n>0and~-f(n/2)or(n==0)*64
Try it online!
Arithmetical alternative.
add a comment |
C (gcc), 14 bytes
__builtin_clzl
Works fine on tio
C (gcc), 35 29 bytes
f(long n){n=n<0?0:f(n-~n)+1;}
Try it online!
Than Dennis for 6 bytes
C (gcc) compiler flags, 29 bytes by David Foerster
-Df(n)=n?__builtin_clzl(n):64
Try it online!
3
Worth noting that it's only for 64-bit machines (or any others with LP64/ILP64/etc. ABI)
– Ruslan
Dec 10 at 6:43
1
Geez, that’s even shorter than any use of the GCC built-in__builtin_clzl
with which I can come up.
– David Foerster
Dec 10 at 11:49
@Ruslan: good point, on systems wherelong
is 32 bits (including Windows x64), you need__builtin_clzll
(unsigned long long). godbolt.org/z/MACCKf. (Unlike Intel intrinsics, GNU C builtins are supported regardless of the operation being doable with one machine instruction. On 32-bit x86, clzll compiles to a branch or cmov to dolzcnt(low half)+32
orlzcnt(high half)
. Orbsr
iflzcnt
isn't available.
– Peter Cordes
Dec 12 at 1:00
The test cases include "0" but__builtin_clz(l)(l)
is undefined behavior for zero: "If x is 0, the result is undefined."
– MCCCS
Dec 12 at 13:36
1
@MCCCS If it works, it counts. That's also why I keep the last answer
– l4m2
Dec 12 at 13:43
add a comment |
Java 8, 32 26 bytes.
Long::numberOfLeadingZeros
Builtins FTW.
-6 bytes thanks to Kevin Cruijssen
Try it online!
Ah, completely forgot aboutnumberOfLeadingZeros
.. You can golf it to 28 bytes btw:n->n.numberOfLeadingZeros(n)
– Kevin Cruijssen
Dec 10 at 10:43
1
Actually,Long::numberOfLeadingZeros
is even shorter (26 bytes).
– Kevin Cruijssen
Dec 10 at 10:46
5
Wow, it doesn't happen very often that Java beats Python. Congrats!
– Eric Duminil
Dec 10 at 18:46
add a comment |
Perl 6, 35 28 26 bytes
-2 bytes thanks to nwellnhof
{to .fmt("%064b")~~/^0*/:}
Try it online!
Anonymous code block that takes a number and returns a number. This converts the number to a binary string and counts the leading zeroes. It works for negative numbers because the first character is a -
e.g. -00000101
, so there are no leading zeroes.
Explanation:
{ } # 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
add a comment |
Python 3, 34 bytes
f=lambda n:-1<n<2**63and-~f(2*n|1)
Try it online!
add a comment |
J, 18 bytes
0{[:I.1,~(64$2)#:]
Try it online!
J, 19 bytes
1#.[:*/=(64$2)#:]
Try it online!
Explanation:
#: - 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) is close but doesn't work for negative numbers :(
– Conor O'Brien
Dec 10 at 22:12
@Conor O'Brien Nice approach too!
– Galen Ivanov
Dec 11 at 4:41
add a comment |
Perl 6, 18 bytes
-2 bytes thanks to Jo King
64-(*%2**64*2).msb
Try it online!
add a comment |
JavaScript (Node.js), 25 bytes
Takes input as a BigInt literal.
f=x=>x<0?0:x?f(x/2n)-1:64
Try it online!
Or 24 bytes by returning false instead of $0$.
Wouldn'tn=>n<1?0:n.toString(2)-64
perform the same?
– Ismael Miguel
Dec 10 at 12:59
@IsmaelMiguel I suppose you meantn=>n<1?0:n.toString(2).length-64
, but that would not work anyway. This would, I think.
– Arnauld
Dec 10 at 13:28
1
@IsmaelMiguel No worries. :) It's indeed possible to have the.toString()
approach working, but we still need a BigInt literal as input. Otherwise, we only have 52 bits of mantissa, leading to invalid results when precision is lost.
– Arnauld
Dec 10 at 13:48
1
The fact that the BigInt suffix is the same character as your parameter is very confusing...
– Neil
Dec 11 at 9:25
1
@Neil Unreadable code on PPCG?? This can't be! Fixed! :p
– Arnauld
Dec 11 at 12:04
|
show 1 more comment
05AB1E, 10 9 bytes
·bg65αsd*
I/O are both integers
Try it online or verify all test cases.
Explanation:
· # 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
add a comment |
APL+WIN, 34 bytes
+/×=(0>n),(63⍴2)⊤((2*63)××n)+n←⎕
Explanation:
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
+/×= Identify zeros, isolate first contiguous group and sum if first element is zero
add a comment |
Haskell, 56 bytes
Thanks xnor for spotting a mistake!
f n|n<0=0|1>0=sum.fst.span(>0)$mapM(pure[1,0])[1..64]!!n
Might allocate quite a lot of memory, try it online!
Maybe you want to test it with a smaller constant: Try 8-bit!
Explanation
Instead of using mapM(pure[0,1])[1..64]
to convert the input to binary, we'll use mapM(pure[1,0])[1..64]
which essentially generates the inverted strings $\{0,1\}^{64}$ in lexicographic order. So we can just sum the $1$s-prefix by using sum.fst.span(>0)
.
add a comment |
Ruby, 22 bytes
->n{/[^0]/=~"%064b"%n}
Try it online!
add a comment |
C# (Visual C# Interactive Compiler), 42 bytes
x=>x!=0?64-Convert.ToString(x,2).Length:64
Try it online!
C# (Visual C# Interactive Compiler), 31 bytes
int c(long x)=>x<0?0:c(x-~x)+1;
Even shorter, based off of @l4m2's C (gcc) answer.
Never knew that you could declare functions like that, thanks @Dana!
Try it online!
1
I think this is valid? tio.run/##ZZA/…
– dana
Dec 11 at 13:17
add a comment |
Jelly, 10 9 bytes
-1 thanks to a neat trick by Erik the Outgolfer (is-non-negative is now simply AƑ
)
ḤBL65_×AƑ
A monadic Link accepting an integer (within range) which yields an integer.
Try it online! Or see the test-suite.
The 10 was ḤBL65_ɓ>-×
Here is another 10 byte solution, which I like since it says it is "BOSS"...
BoṠS»-~%65
Test-suite here
...BoṠS63r0¤i
, BoṠS63ŻṚ¤i
, or BoṠS64ḶṚ¤i
would also work.
Another 10 byter (from Dennis) is æ»64ḶṚ¤Äċ0
(again æ»63r0¤Äċ0
and æ»63ŻṚ¤Äċ0
will also work)
9 bytes
– Erik the Outgolfer
Dec 11 at 18:18
@EriktheOutgolfer I thought to myself "there must be a golfier way to multiply by isNonNegative" and didn't think of theƑ
quick at all, very nice work!
– Jonathan Allan
Dec 11 at 19:11
1
Actually, I've been theorizing aboutAƑ
for quite some while now. Be warned that it doesn't vectorize! ;-) It's actually "flatten and then check if all elements are nonnegative".
– Erik the Outgolfer
Dec 11 at 19:14
add a comment |
Powershell, 51 bytes
param([long]$n)for(;$n-shl$i++-gt0){}($i,65)[!$n]-1
Test script:
$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"
}
Output:
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
add a comment |
Java 8, 38 bytes
int f(long n){return n<0?0:f(n-~n)+1;}
Input as long
(64-bit integer), output as int
(32-bit integer).
Port of @l4m2's C (gcc) answer.
Try it online.
Explanation:
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
EDIT: Can be 26 bytes by using the builtin Long::numberOfLeadingZeros
as displayed in @lukeg's Java 8 answer.
add a comment |
Perl 5, 37 bytes
sub{sprintf("%064b",@_)=~/^0*/;$+[0]}
Try it online!
Or this 46 bytes if the "stringification" is not allowed: sub z
sub{my$i=0;$_[0]>>64-$_?last:$i++for 1..64;$i}
s/length$&/$+[0]/
(-3 bytes) ;)
– Dada
Dec 10 at 12:59
IMO, you're not allowed to remove thesub
keyword from answers containing Perl 5 functions.
– nwellnhof
Dec 10 at 14:36
I've seen whats similar to removingsub
in answers for other languages, perl6, powershell and more.
– Kjetil S.
Dec 10 at 14:58
In Perl6, I think you don't needsub{}
to make a (anonymous?) sub, which explain why it's omitted from Perl6 answers. I agree with @nwellnhof that you shouldn't be allowed to removesub
. (when I was still active, like a year ago or so, that was the rule)
– Dada
Dec 10 at 15:03
changed now. And included$+[0]
.
– Kjetil S.
Dec 10 at 15:10
add a comment |
Swift (on a 64-bit platform), 41 bytes
Declares a closure called f
which accepts and returns an Int
. This solution only works correctly 64-bit platforms, where Int
is typealias
ed to Int64
. (On a 32-bit platform, Int64
can be used explicitly for the closure’s parameter type, adding 2 bytes.)
let f:(Int)->Int={$0.leadingZeroBitCount}
In Swift, even the fundamental integer type is an ordinary object declared in the standard library. This means Int
can have methods and properties, such as leadingZeroBitCount
(which is required on all types conforming to the standard library’s FixedWidthInteger
protocol).
add a comment |
Clean, 103 bytes
Uses the same "builtin" as ceilingcat's answer.
f::!Int->Int
f _=code {
instruction 243
instruction 72
instruction 15
instruction 189
instruction 192
}
Try it online!
Clean, 58 bytes
import StdEnv
$0=64
$i=until(e=(2^63>>e)bitand i<>0)inc 0
Try it online!
add a comment |
Stax, 10 bytes
în»╧3(∞┼⌠g
Run and debug it
It's a port of Kevin's 05AB1E solution.
add a comment |
Perl 5 -p
, 42 bytes
1while$_>0&&2**++$a-1<$_;$_=0|$_>=0&&64-$a
Try it online!
Longer than a bitstring based solution, but a decent math based solution.
Doesn't really work if I'm not mistaken
– Dada
Dec 11 at 12:23
@Dada I see that there are a few cases where the floating point division doesn't quite work out properly. I put in anint
call that should solve the issue.
– Xcali
Dec 11 at 15:55
Sorry, I failed my copy-past it would seem. This is what I wanted to send ;)
– Dada
Dec 11 at 17:36
add a comment |
APL(NARS), 15 chars, 30 bytes
{¯1+1⍳⍨⍵⊤⍨64⍴2}
test for few numbers for see how to use:
f←{¯1+1⍳⍨⍵⊤⍨64⍴2}
f ¯9223372036854775808
0
f 9223372036854775807
1
add a comment |
K (ngn/k), 6 bytes
64-#2
Try it online!
2
encode the argument in binary
#
length
64-
subtract from 64
# = length
... looks string based
– Titus
Dec 13 at 14:37
2
@Titus2
gives a list of integers and#
finds its length. no strings are involved here.
– ngn
Dec 13 at 15:38
add a comment |
PHP, 50 46 bytes
for(;0<$n=&$argn;$n>>=1)$i++;echo$n<0?0:64-$i;
Run as pipe with -R
or try it online,
<?=$argn<0?0:0|64-log($argn+1,2);
has rounding issues; so I took the long way.
add a comment |
Wolfram Language (Mathematica), 41 bytes
The formula for positive numbers is just 63-Floor@Log2@#&
. Replacement rules are used for the special cases of zero and negative input.
The input need not be a 64-bit signed integer. This will effectively take the floor of the input to turn it into an integer. If you input a number outside of the normal bounds for a 64-bit integer, it will tell return a negative number indicating how many more bits would be needed to store this integer.
63-Floor@Log2[#/.{_?(#<0&):>2^63,0:>.5}]&
Try it online!
@LegionMammal978's solution is quite a bit shorter at 28 bytes. The input must be an integer. Per the documentation: "BitLength[n]
is effectively an efficient version of Floor[Log[2,n]]+1
. " It automatically handles the case of zero correctly reporting 0
rather than -∞
.
Wolfram Language (Mathematica), 28 bytes
Boole[#>=0](64-BitLength@#)&
Try it online!
1
Boole[#>=0](64-BitLength@#)&
is a good bit shorter at 28 bytes. It uses the same basic concept as yours, but appliesBitLength
andBoole
.
– LegionMammal978
Dec 12 at 2:13
I totally forgot about BitLength!
– Kelly Lowder
Dec 14 at 2:29
add a comment |
Charcoal, 15 bytes
I⁻⁶⁴L↨﹪NX²¦⁶⁴¦²
Try it online! Link is to verbose version of code. Explanation:
L Length of
N Input as a number
﹪ Modulo
² Literal 2
X To the power
⁶⁴ Literal 64
↨ Converted to base
² Literal 2
⁻ Subtracted from
⁶⁴ Literal 64
I Cast to string
Implicitly print
The ¦
s serve to separate adjacent integer literals. Conveniently, Charcoal's arbitrary numeric base conversion converts 0
into an empty list, however for negative numbers it simply inverts the sign of each digit, so the number is converted to the equivalent unsigned 64-bit integer first.
add a comment |
Rust, 18 bytes
i64::leading_zeros
Try it online!
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "200"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f177271%2ffind-the-number-of-leading-zeroes-in-a-64-bit-integer%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
29 Answers
29
active
oldest
votes
29 Answers
29
active
oldest
votes
active
oldest
votes
active
oldest
votes
x86_64 machine language on Linux, 6 bytes
0: f3 48 0f bd c7 lzcnt %rdi,%rax
5: c3 ret
Requires Haswell or K10 or higher processor with lzcnt
instruction.
Try it online!
18
Builtins strike again /s
– Logern
Dec 10 at 2:06
1
I recommend specifying the calling convention used (though you did say on Linux)
– qwr
Dec 12 at 8:02
@qwr It looks like SysV calling convention because the parameter is passed in %rdi and it is returned in %rax.
– Logern
Dec 15 at 4:21
add a comment |
x86_64 machine language on Linux, 6 bytes
0: f3 48 0f bd c7 lzcnt %rdi,%rax
5: c3 ret
Requires Haswell or K10 or higher processor with lzcnt
instruction.
Try it online!
18
Builtins strike again /s
– Logern
Dec 10 at 2:06
1
I recommend specifying the calling convention used (though you did say on Linux)
– qwr
Dec 12 at 8:02
@qwr It looks like SysV calling convention because the parameter is passed in %rdi and it is returned in %rax.
– Logern
Dec 15 at 4:21
add a comment |
x86_64 machine language on Linux, 6 bytes
0: f3 48 0f bd c7 lzcnt %rdi,%rax
5: c3 ret
Requires Haswell or K10 or higher processor with lzcnt
instruction.
Try it online!
x86_64 machine language on Linux, 6 bytes
0: f3 48 0f bd c7 lzcnt %rdi,%rax
5: c3 ret
Requires Haswell or K10 or higher processor with lzcnt
instruction.
Try it online!
edited Dec 10 at 9:25
answered Dec 10 at 0:07
ceilingcat
3,3991820
3,3991820
18
Builtins strike again /s
– Logern
Dec 10 at 2:06
1
I recommend specifying the calling convention used (though you did say on Linux)
– qwr
Dec 12 at 8:02
@qwr It looks like SysV calling convention because the parameter is passed in %rdi and it is returned in %rax.
– Logern
Dec 15 at 4:21
add a comment |
18
Builtins strike again /s
– Logern
Dec 10 at 2:06
1
I recommend specifying the calling convention used (though you did say on Linux)
– qwr
Dec 12 at 8:02
@qwr It looks like SysV calling convention because the parameter is passed in %rdi and it is returned in %rax.
– Logern
Dec 15 at 4:21
18
18
Builtins strike again /s
– Logern
Dec 10 at 2:06
Builtins strike again /s
– Logern
Dec 10 at 2:06
1
1
I recommend specifying the calling convention used (though you did say on Linux)
– qwr
Dec 12 at 8:02
I recommend specifying the calling convention used (though you did say on Linux)
– qwr
Dec 12 at 8:02
@qwr It looks like SysV calling convention because the parameter is passed in %rdi and it is returned in %rax.
– Logern
Dec 15 at 4:21
@qwr It looks like SysV calling convention because the parameter is passed in %rdi and it is returned in %rax.
– Logern
Dec 15 at 4:21
add a comment |
Hexagony, 78 70 bytes
2"1".}/{}A=<?>(<$*}[_(A".{}."&.'&=/.."!=2'%<..(@.>._.={}:"<><$
Try it online!
Isn't this challenge too trivial for a practical language? ;)
side length 6. I can't fit it in a side length 5 hexagon.
Explanation
3
I laughed really hard at the "explanation". :D
– Eric Duminil
Dec 10 at 18:45
1
I think you may have overcomplicated handling negative numbers/zero. I managed to fit a similar program into side length 5 by not doing that hefty 2^64 calculation. It clearly isn't well golfed yet, though!
– FryAmTheEggman
Dec 10 at 22:56
@fry Ah right, negative numbers always have 0 leading zeroes... which definitely leads to shorter program because generates 2^64 is long.
– user202729
Dec 11 at 5:39
add a comment |
Hexagony, 78 70 bytes
2"1".}/{}A=<?>(<$*}[_(A".{}."&.'&=/.."!=2'%<..(@.>._.={}:"<><$
Try it online!
Isn't this challenge too trivial for a practical language? ;)
side length 6. I can't fit it in a side length 5 hexagon.
Explanation
3
I laughed really hard at the "explanation". :D
– Eric Duminil
Dec 10 at 18:45
1
I think you may have overcomplicated handling negative numbers/zero. I managed to fit a similar program into side length 5 by not doing that hefty 2^64 calculation. It clearly isn't well golfed yet, though!
– FryAmTheEggman
Dec 10 at 22:56
@fry Ah right, negative numbers always have 0 leading zeroes... which definitely leads to shorter program because generates 2^64 is long.
– user202729
Dec 11 at 5:39
add a comment |
Hexagony, 78 70 bytes
2"1".}/{}A=<?>(<$*}[_(A".{}."&.'&=/.."!=2'%<..(@.>._.={}:"<><$
Try it online!
Isn't this challenge too trivial for a practical language? ;)
side length 6. I can't fit it in a side length 5 hexagon.
Explanation
Hexagony, 78 70 bytes
2"1".}/{}A=<?>(<$*}[_(A".{}."&.'&=/.."!=2'%<..(@.>._.={}:"<><$
Try it online!
Isn't this challenge too trivial for a practical language? ;)
side length 6. I can't fit it in a side length 5 hexagon.
Explanation
edited Dec 10 at 16:21
answered Dec 10 at 15:10
user202729
13.9k12551
13.9k12551
3
I laughed really hard at the "explanation". :D
– Eric Duminil
Dec 10 at 18:45
1
I think you may have overcomplicated handling negative numbers/zero. I managed to fit a similar program into side length 5 by not doing that hefty 2^64 calculation. It clearly isn't well golfed yet, though!
– FryAmTheEggman
Dec 10 at 22:56
@fry Ah right, negative numbers always have 0 leading zeroes... which definitely leads to shorter program because generates 2^64 is long.
– user202729
Dec 11 at 5:39
add a comment |
3
I laughed really hard at the "explanation". :D
– Eric Duminil
Dec 10 at 18:45
1
I think you may have overcomplicated handling negative numbers/zero. I managed to fit a similar program into side length 5 by not doing that hefty 2^64 calculation. It clearly isn't well golfed yet, though!
– FryAmTheEggman
Dec 10 at 22:56
@fry Ah right, negative numbers always have 0 leading zeroes... which definitely leads to shorter program because generates 2^64 is long.
– user202729
Dec 11 at 5:39
3
3
I laughed really hard at the "explanation". :D
– Eric Duminil
Dec 10 at 18:45
I laughed really hard at the "explanation". :D
– Eric Duminil
Dec 10 at 18:45
1
1
I think you may have overcomplicated handling negative numbers/zero. I managed to fit a similar program into side length 5 by not doing that hefty 2^64 calculation. It clearly isn't well golfed yet, though!
– FryAmTheEggman
Dec 10 at 22:56
I think you may have overcomplicated handling negative numbers/zero. I managed to fit a similar program into side length 5 by not doing that hefty 2^64 calculation. It clearly isn't well golfed yet, though!
– FryAmTheEggman
Dec 10 at 22:56
@fry Ah right, negative numbers always have 0 leading zeroes... which definitely leads to shorter program because generates 2^64 is long.
– user202729
Dec 11 at 5:39
@fry Ah right, negative numbers always have 0 leading zeroes... which definitely leads to shorter program because generates 2^64 is long.
– user202729
Dec 11 at 5:39
add a comment |
Python, 31 bytes
lambda n:67-len(bin(-n))&~n>>64
Try it online!
The expresson is the bitwise &
of two parts:
67-len(bin(-n)) & ~n>>64
The 67-len(bin(-n))
gives the correct answer for non-negative inputs. It takes the bit length, and subtracts from 67, which is 3 more than 64 to compensate for the -0b
prefix. The negation is a trick to adjust for n==0
using that negating it doesn't produce a -
sign in front.
The & ~n>>64
makes the answer instead be 0
for negative n
. When n<0
, ~n>>64
equals 0 (on 64-bit integers), so and-ing with it gives 0
. When n>=0
, the ~n>>64
evaluates to -1
, and doing &-1
has no effect.
Python 2, 36 bytes
f=lambda n:n>0and~-f(n/2)or(n==0)*64
Try it online!
Arithmetical alternative.
add a comment |
Python, 31 bytes
lambda n:67-len(bin(-n))&~n>>64
Try it online!
The expresson is the bitwise &
of two parts:
67-len(bin(-n)) & ~n>>64
The 67-len(bin(-n))
gives the correct answer for non-negative inputs. It takes the bit length, and subtracts from 67, which is 3 more than 64 to compensate for the -0b
prefix. The negation is a trick to adjust for n==0
using that negating it doesn't produce a -
sign in front.
The & ~n>>64
makes the answer instead be 0
for negative n
. When n<0
, ~n>>64
equals 0 (on 64-bit integers), so and-ing with it gives 0
. When n>=0
, the ~n>>64
evaluates to -1
, and doing &-1
has no effect.
Python 2, 36 bytes
f=lambda n:n>0and~-f(n/2)or(n==0)*64
Try it online!
Arithmetical alternative.
add a comment |
Python, 31 bytes
lambda n:67-len(bin(-n))&~n>>64
Try it online!
The expresson is the bitwise &
of two parts:
67-len(bin(-n)) & ~n>>64
The 67-len(bin(-n))
gives the correct answer for non-negative inputs. It takes the bit length, and subtracts from 67, which is 3 more than 64 to compensate for the -0b
prefix. The negation is a trick to adjust for n==0
using that negating it doesn't produce a -
sign in front.
The & ~n>>64
makes the answer instead be 0
for negative n
. When n<0
, ~n>>64
equals 0 (on 64-bit integers), so and-ing with it gives 0
. When n>=0
, the ~n>>64
evaluates to -1
, and doing &-1
has no effect.
Python 2, 36 bytes
f=lambda n:n>0and~-f(n/2)or(n==0)*64
Try it online!
Arithmetical alternative.
Python, 31 bytes
lambda n:67-len(bin(-n))&~n>>64
Try it online!
The expresson is the bitwise &
of two parts:
67-len(bin(-n)) & ~n>>64
The 67-len(bin(-n))
gives the correct answer for non-negative inputs. It takes the bit length, and subtracts from 67, which is 3 more than 64 to compensate for the -0b
prefix. The negation is a trick to adjust for n==0
using that negating it doesn't produce a -
sign in front.
The & ~n>>64
makes the answer instead be 0
for negative n
. When n<0
, ~n>>64
equals 0 (on 64-bit integers), so and-ing with it gives 0
. When n>=0
, the ~n>>64
evaluates to -1
, and doing &-1
has no effect.
Python 2, 36 bytes
f=lambda n:n>0and~-f(n/2)or(n==0)*64
Try it online!
Arithmetical alternative.
edited Dec 10 at 0:16
answered Dec 9 at 23:57
xnor
89.7k18184439
89.7k18184439
add a comment |
add a comment |
C (gcc), 14 bytes
__builtin_clzl
Works fine on tio
C (gcc), 35 29 bytes
f(long n){n=n<0?0:f(n-~n)+1;}
Try it online!
Than Dennis for 6 bytes
C (gcc) compiler flags, 29 bytes by David Foerster
-Df(n)=n?__builtin_clzl(n):64
Try it online!
3
Worth noting that it's only for 64-bit machines (or any others with LP64/ILP64/etc. ABI)
– Ruslan
Dec 10 at 6:43
1
Geez, that’s even shorter than any use of the GCC built-in__builtin_clzl
with which I can come up.
– David Foerster
Dec 10 at 11:49
@Ruslan: good point, on systems wherelong
is 32 bits (including Windows x64), you need__builtin_clzll
(unsigned long long). godbolt.org/z/MACCKf. (Unlike Intel intrinsics, GNU C builtins are supported regardless of the operation being doable with one machine instruction. On 32-bit x86, clzll compiles to a branch or cmov to dolzcnt(low half)+32
orlzcnt(high half)
. Orbsr
iflzcnt
isn't available.
– Peter Cordes
Dec 12 at 1:00
The test cases include "0" but__builtin_clz(l)(l)
is undefined behavior for zero: "If x is 0, the result is undefined."
– MCCCS
Dec 12 at 13:36
1
@MCCCS If it works, it counts. That's also why I keep the last answer
– l4m2
Dec 12 at 13:43
add a comment |
C (gcc), 14 bytes
__builtin_clzl
Works fine on tio
C (gcc), 35 29 bytes
f(long n){n=n<0?0:f(n-~n)+1;}
Try it online!
Than Dennis for 6 bytes
C (gcc) compiler flags, 29 bytes by David Foerster
-Df(n)=n?__builtin_clzl(n):64
Try it online!
3
Worth noting that it's only for 64-bit machines (or any others with LP64/ILP64/etc. ABI)
– Ruslan
Dec 10 at 6:43
1
Geez, that’s even shorter than any use of the GCC built-in__builtin_clzl
with which I can come up.
– David Foerster
Dec 10 at 11:49
@Ruslan: good point, on systems wherelong
is 32 bits (including Windows x64), you need__builtin_clzll
(unsigned long long). godbolt.org/z/MACCKf. (Unlike Intel intrinsics, GNU C builtins are supported regardless of the operation being doable with one machine instruction. On 32-bit x86, clzll compiles to a branch or cmov to dolzcnt(low half)+32
orlzcnt(high half)
. Orbsr
iflzcnt
isn't available.
– Peter Cordes
Dec 12 at 1:00
The test cases include "0" but__builtin_clz(l)(l)
is undefined behavior for zero: "If x is 0, the result is undefined."
– MCCCS
Dec 12 at 13:36
1
@MCCCS If it works, it counts. That's also why I keep the last answer
– l4m2
Dec 12 at 13:43
add a comment |
C (gcc), 14 bytes
__builtin_clzl
Works fine on tio
C (gcc), 35 29 bytes
f(long n){n=n<0?0:f(n-~n)+1;}
Try it online!
Than Dennis for 6 bytes
C (gcc) compiler flags, 29 bytes by David Foerster
-Df(n)=n?__builtin_clzl(n):64
Try it online!
C (gcc), 14 bytes
__builtin_clzl
Works fine on tio
C (gcc), 35 29 bytes
f(long n){n=n<0?0:f(n-~n)+1;}
Try it online!
Than Dennis for 6 bytes
C (gcc) compiler flags, 29 bytes by David Foerster
-Df(n)=n?__builtin_clzl(n):64
Try it online!
edited Dec 10 at 12:13
answered Dec 10 at 4:18
l4m2
4,6281634
4,6281634
3
Worth noting that it's only for 64-bit machines (or any others with LP64/ILP64/etc. ABI)
– Ruslan
Dec 10 at 6:43
1
Geez, that’s even shorter than any use of the GCC built-in__builtin_clzl
with which I can come up.
– David Foerster
Dec 10 at 11:49
@Ruslan: good point, on systems wherelong
is 32 bits (including Windows x64), you need__builtin_clzll
(unsigned long long). godbolt.org/z/MACCKf. (Unlike Intel intrinsics, GNU C builtins are supported regardless of the operation being doable with one machine instruction. On 32-bit x86, clzll compiles to a branch or cmov to dolzcnt(low half)+32
orlzcnt(high half)
. Orbsr
iflzcnt
isn't available.
– Peter Cordes
Dec 12 at 1:00
The test cases include "0" but__builtin_clz(l)(l)
is undefined behavior for zero: "If x is 0, the result is undefined."
– MCCCS
Dec 12 at 13:36
1
@MCCCS If it works, it counts. That's also why I keep the last answer
– l4m2
Dec 12 at 13:43
add a comment |
3
Worth noting that it's only for 64-bit machines (or any others with LP64/ILP64/etc. ABI)
– Ruslan
Dec 10 at 6:43
1
Geez, that’s even shorter than any use of the GCC built-in__builtin_clzl
with which I can come up.
– David Foerster
Dec 10 at 11:49
@Ruslan: good point, on systems wherelong
is 32 bits (including Windows x64), you need__builtin_clzll
(unsigned long long). godbolt.org/z/MACCKf. (Unlike Intel intrinsics, GNU C builtins are supported regardless of the operation being doable with one machine instruction. On 32-bit x86, clzll compiles to a branch or cmov to dolzcnt(low half)+32
orlzcnt(high half)
. Orbsr
iflzcnt
isn't available.
– Peter Cordes
Dec 12 at 1:00
The test cases include "0" but__builtin_clz(l)(l)
is undefined behavior for zero: "If x is 0, the result is undefined."
– MCCCS
Dec 12 at 13:36
1
@MCCCS If it works, it counts. That's also why I keep the last answer
– l4m2
Dec 12 at 13:43
3
3
Worth noting that it's only for 64-bit machines (or any others with LP64/ILP64/etc. ABI)
– Ruslan
Dec 10 at 6:43
Worth noting that it's only for 64-bit machines (or any others with LP64/ILP64/etc. ABI)
– Ruslan
Dec 10 at 6:43
1
1
Geez, that’s even shorter than any use of the GCC built-in
__builtin_clzl
with which I can come up.– David Foerster
Dec 10 at 11:49
Geez, that’s even shorter than any use of the GCC built-in
__builtin_clzl
with which I can come up.– David Foerster
Dec 10 at 11:49
@Ruslan: good point, on systems where
long
is 32 bits (including Windows x64), you need __builtin_clzll
(unsigned long long). godbolt.org/z/MACCKf. (Unlike Intel intrinsics, GNU C builtins are supported regardless of the operation being doable with one machine instruction. On 32-bit x86, clzll compiles to a branch or cmov to do lzcnt(low half)+32
or lzcnt(high half)
. Or bsr
if lzcnt
isn't available.– Peter Cordes
Dec 12 at 1:00
@Ruslan: good point, on systems where
long
is 32 bits (including Windows x64), you need __builtin_clzll
(unsigned long long). godbolt.org/z/MACCKf. (Unlike Intel intrinsics, GNU C builtins are supported regardless of the operation being doable with one machine instruction. On 32-bit x86, clzll compiles to a branch or cmov to do lzcnt(low half)+32
or lzcnt(high half)
. Or bsr
if lzcnt
isn't available.– Peter Cordes
Dec 12 at 1:00
The test cases include "0" but
__builtin_clz(l)(l)
is undefined behavior for zero: "If x is 0, the result is undefined."– MCCCS
Dec 12 at 13:36
The test cases include "0" but
__builtin_clz(l)(l)
is undefined behavior for zero: "If x is 0, the result is undefined."– MCCCS
Dec 12 at 13:36
1
1
@MCCCS If it works, it counts. That's also why I keep the last answer
– l4m2
Dec 12 at 13:43
@MCCCS If it works, it counts. That's also why I keep the last answer
– l4m2
Dec 12 at 13:43
add a comment |
Java 8, 32 26 bytes.
Long::numberOfLeadingZeros
Builtins FTW.
-6 bytes thanks to Kevin Cruijssen
Try it online!
Ah, completely forgot aboutnumberOfLeadingZeros
.. You can golf it to 28 bytes btw:n->n.numberOfLeadingZeros(n)
– Kevin Cruijssen
Dec 10 at 10:43
1
Actually,Long::numberOfLeadingZeros
is even shorter (26 bytes).
– Kevin Cruijssen
Dec 10 at 10:46
5
Wow, it doesn't happen very often that Java beats Python. Congrats!
– Eric Duminil
Dec 10 at 18:46
add a comment |
Java 8, 32 26 bytes.
Long::numberOfLeadingZeros
Builtins FTW.
-6 bytes thanks to Kevin Cruijssen
Try it online!
Ah, completely forgot aboutnumberOfLeadingZeros
.. You can golf it to 28 bytes btw:n->n.numberOfLeadingZeros(n)
– Kevin Cruijssen
Dec 10 at 10:43
1
Actually,Long::numberOfLeadingZeros
is even shorter (26 bytes).
– Kevin Cruijssen
Dec 10 at 10:46
5
Wow, it doesn't happen very often that Java beats Python. Congrats!
– Eric Duminil
Dec 10 at 18:46
add a comment |
Java 8, 32 26 bytes.
Long::numberOfLeadingZeros
Builtins FTW.
-6 bytes thanks to Kevin Cruijssen
Try it online!
Java 8, 32 26 bytes.
Long::numberOfLeadingZeros
Builtins FTW.
-6 bytes thanks to Kevin Cruijssen
Try it online!
edited Dec 10 at 10:51
answered Dec 10 at 10:39
lukeg
1813
1813
Ah, completely forgot aboutnumberOfLeadingZeros
.. You can golf it to 28 bytes btw:n->n.numberOfLeadingZeros(n)
– Kevin Cruijssen
Dec 10 at 10:43
1
Actually,Long::numberOfLeadingZeros
is even shorter (26 bytes).
– Kevin Cruijssen
Dec 10 at 10:46
5
Wow, it doesn't happen very often that Java beats Python. Congrats!
– Eric Duminil
Dec 10 at 18:46
add a comment |
Ah, completely forgot aboutnumberOfLeadingZeros
.. You can golf it to 28 bytes btw:n->n.numberOfLeadingZeros(n)
– Kevin Cruijssen
Dec 10 at 10:43
1
Actually,Long::numberOfLeadingZeros
is even shorter (26 bytes).
– Kevin Cruijssen
Dec 10 at 10:46
5
Wow, it doesn't happen very often that Java beats Python. Congrats!
– Eric Duminil
Dec 10 at 18:46
Ah, completely forgot about
numberOfLeadingZeros
.. You can golf it to 28 bytes btw: n->n.numberOfLeadingZeros(n)
– Kevin Cruijssen
Dec 10 at 10:43
Ah, completely forgot about
numberOfLeadingZeros
.. You can golf it to 28 bytes btw: n->n.numberOfLeadingZeros(n)
– Kevin Cruijssen
Dec 10 at 10:43
1
1
Actually,
Long::numberOfLeadingZeros
is even shorter (26 bytes).– Kevin Cruijssen
Dec 10 at 10:46
Actually,
Long::numberOfLeadingZeros
is even shorter (26 bytes).– Kevin Cruijssen
Dec 10 at 10:46
5
5
Wow, it doesn't happen very often that Java beats Python. Congrats!
– Eric Duminil
Dec 10 at 18:46
Wow, it doesn't happen very often that Java beats Python. Congrats!
– Eric Duminil
Dec 10 at 18:46
add a comment |
Perl 6, 35 28 26 bytes
-2 bytes thanks to nwellnhof
{to .fmt("%064b")~~/^0*/:}
Try it online!
Anonymous code block that takes a number and returns a number. This converts the number to a binary string and counts the leading zeroes. It works for negative numbers because the first character is a -
e.g. -00000101
, so there are no leading zeroes.
Explanation:
{ } # 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
add a comment |
Perl 6, 35 28 26 bytes
-2 bytes thanks to nwellnhof
{to .fmt("%064b")~~/^0*/:}
Try it online!
Anonymous code block that takes a number and returns a number. This converts the number to a binary string and counts the leading zeroes. It works for negative numbers because the first character is a -
e.g. -00000101
, so there are no leading zeroes.
Explanation:
{ } # 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
add a comment |
Perl 6, 35 28 26 bytes
-2 bytes thanks to nwellnhof
{to .fmt("%064b")~~/^0*/:}
Try it online!
Anonymous code block that takes a number and returns a number. This converts the number to a binary string and counts the leading zeroes. It works for negative numbers because the first character is a -
e.g. -00000101
, so there are no leading zeroes.
Explanation:
{ } # 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
Perl 6, 35 28 26 bytes
-2 bytes thanks to nwellnhof
{to .fmt("%064b")~~/^0*/:}
Try it online!
Anonymous code block that takes a number and returns a number. This converts the number to a binary string and counts the leading zeroes. It works for negative numbers because the first character is a -
e.g. -00000101
, so there are no leading zeroes.
Explanation:
{ } # 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
edited Dec 11 at 11:44
answered Dec 9 at 23:31
Jo King
20.7k247109
20.7k247109
add a comment |
add a comment |
Python 3, 34 bytes
f=lambda n:-1<n<2**63and-~f(2*n|1)
Try it online!
add a comment |
Python 3, 34 bytes
f=lambda n:-1<n<2**63and-~f(2*n|1)
Try it online!
add a comment |
Python 3, 34 bytes
f=lambda n:-1<n<2**63and-~f(2*n|1)
Try it online!
Python 3, 34 bytes
f=lambda n:-1<n<2**63and-~f(2*n|1)
Try it online!
answered Dec 9 at 23:55
ovs
18.7k21059
18.7k21059
add a comment |
add a comment |
J, 18 bytes
0{[:I.1,~(64$2)#:]
Try it online!
J, 19 bytes
1#.[:*/=(64$2)#:]
Try it online!
Explanation:
#: - 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) is close but doesn't work for negative numbers :(
– Conor O'Brien
Dec 10 at 22:12
@Conor O'Brien Nice approach too!
– Galen Ivanov
Dec 11 at 4:41
add a comment |
J, 18 bytes
0{[:I.1,~(64$2)#:]
Try it online!
J, 19 bytes
1#.[:*/=(64$2)#:]
Try it online!
Explanation:
#: - 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) is close but doesn't work for negative numbers :(
– Conor O'Brien
Dec 10 at 22:12
@Conor O'Brien Nice approach too!
– Galen Ivanov
Dec 11 at 4:41
add a comment |
J, 18 bytes
0{[:I.1,~(64$2)#:]
Try it online!
J, 19 bytes
1#.[:*/=(64$2)#:]
Try it online!
Explanation:
#: - convert
] - the input to
(64$2) - 64 binary digits
= - check if each digit equals
0 - zero
[:*/ - find the running product
1#. - sum
J, 18 bytes
0{[:I.1,~(64$2)#:]
Try it online!
J, 19 bytes
1#.[:*/=(64$2)#:]
Try it online!
Explanation:
#: - convert
] - the input to
(64$2) - 64 binary digits
= - check if each digit equals
0 - zero
[:*/ - find the running product
1#. - sum
edited Dec 10 at 10:19
answered Dec 10 at 8:52
Galen Ivanov
6,31711032
6,31711032
1
1#.[:*/1-_64{.#:
(17) is close but doesn't work for negative numbers :(
– Conor O'Brien
Dec 10 at 22:12
@Conor O'Brien Nice approach too!
– Galen Ivanov
Dec 11 at 4:41
add a comment |
1
1#.[:*/1-_64{.#:
(17) is close but doesn't work for negative numbers :(
– Conor O'Brien
Dec 10 at 22:12
@Conor O'Brien Nice approach too!
– Galen Ivanov
Dec 11 at 4:41
1
1
1#.[:*/1-_64{.#:
(17) is close but doesn't work for negative numbers :(– Conor O'Brien
Dec 10 at 22:12
1#.[:*/1-_64{.#:
(17) is close but doesn't work for negative numbers :(– Conor O'Brien
Dec 10 at 22:12
@Conor O'Brien Nice approach too!
– Galen Ivanov
Dec 11 at 4:41
@Conor O'Brien Nice approach too!
– Galen Ivanov
Dec 11 at 4:41
add a comment |
Perl 6, 18 bytes
-2 bytes thanks to Jo King
64-(*%2**64*2).msb
Try it online!
add a comment |
Perl 6, 18 bytes
-2 bytes thanks to Jo King
64-(*%2**64*2).msb
Try it online!
add a comment |
Perl 6, 18 bytes
-2 bytes thanks to Jo King
64-(*%2**64*2).msb
Try it online!
Perl 6, 18 bytes
-2 bytes thanks to Jo King
64-(*%2**64*2).msb
Try it online!
answered Dec 10 at 13:36
nwellnhof
6,48511125
6,48511125
add a comment |
add a comment |
JavaScript (Node.js), 25 bytes
Takes input as a BigInt literal.
f=x=>x<0?0:x?f(x/2n)-1:64
Try it online!
Or 24 bytes by returning false instead of $0$.
Wouldn'tn=>n<1?0:n.toString(2)-64
perform the same?
– Ismael Miguel
Dec 10 at 12:59
@IsmaelMiguel I suppose you meantn=>n<1?0:n.toString(2).length-64
, but that would not work anyway. This would, I think.
– Arnauld
Dec 10 at 13:28
1
@IsmaelMiguel No worries. :) It's indeed possible to have the.toString()
approach working, but we still need a BigInt literal as input. Otherwise, we only have 52 bits of mantissa, leading to invalid results when precision is lost.
– Arnauld
Dec 10 at 13:48
1
The fact that the BigInt suffix is the same character as your parameter is very confusing...
– Neil
Dec 11 at 9:25
1
@Neil Unreadable code on PPCG?? This can't be! Fixed! :p
– Arnauld
Dec 11 at 12:04
|
show 1 more comment
JavaScript (Node.js), 25 bytes
Takes input as a BigInt literal.
f=x=>x<0?0:x?f(x/2n)-1:64
Try it online!
Or 24 bytes by returning false instead of $0$.
Wouldn'tn=>n<1?0:n.toString(2)-64
perform the same?
– Ismael Miguel
Dec 10 at 12:59
@IsmaelMiguel I suppose you meantn=>n<1?0:n.toString(2).length-64
, but that would not work anyway. This would, I think.
– Arnauld
Dec 10 at 13:28
1
@IsmaelMiguel No worries. :) It's indeed possible to have the.toString()
approach working, but we still need a BigInt literal as input. Otherwise, we only have 52 bits of mantissa, leading to invalid results when precision is lost.
– Arnauld
Dec 10 at 13:48
1
The fact that the BigInt suffix is the same character as your parameter is very confusing...
– Neil
Dec 11 at 9:25
1
@Neil Unreadable code on PPCG?? This can't be! Fixed! :p
– Arnauld
Dec 11 at 12:04
|
show 1 more comment
JavaScript (Node.js), 25 bytes
Takes input as a BigInt literal.
f=x=>x<0?0:x?f(x/2n)-1:64
Try it online!
Or 24 bytes by returning false instead of $0$.
JavaScript (Node.js), 25 bytes
Takes input as a BigInt literal.
f=x=>x<0?0:x?f(x/2n)-1:64
Try it online!
Or 24 bytes by returning false instead of $0$.
edited Dec 11 at 12:01
answered Dec 9 at 23:19
Arnauld
72.4k689303
72.4k689303
Wouldn'tn=>n<1?0:n.toString(2)-64
perform the same?
– Ismael Miguel
Dec 10 at 12:59
@IsmaelMiguel I suppose you meantn=>n<1?0:n.toString(2).length-64
, but that would not work anyway. This would, I think.
– Arnauld
Dec 10 at 13:28
1
@IsmaelMiguel No worries. :) It's indeed possible to have the.toString()
approach working, but we still need a BigInt literal as input. Otherwise, we only have 52 bits of mantissa, leading to invalid results when precision is lost.
– Arnauld
Dec 10 at 13:48
1
The fact that the BigInt suffix is the same character as your parameter is very confusing...
– Neil
Dec 11 at 9:25
1
@Neil Unreadable code on PPCG?? This can't be! Fixed! :p
– Arnauld
Dec 11 at 12:04
|
show 1 more comment
Wouldn'tn=>n<1?0:n.toString(2)-64
perform the same?
– Ismael Miguel
Dec 10 at 12:59
@IsmaelMiguel I suppose you meantn=>n<1?0:n.toString(2).length-64
, but that would not work anyway. This would, I think.
– Arnauld
Dec 10 at 13:28
1
@IsmaelMiguel No worries. :) It's indeed possible to have the.toString()
approach working, but we still need a BigInt literal as input. Otherwise, we only have 52 bits of mantissa, leading to invalid results when precision is lost.
– Arnauld
Dec 10 at 13:48
1
The fact that the BigInt suffix is the same character as your parameter is very confusing...
– Neil
Dec 11 at 9:25
1
@Neil Unreadable code on PPCG?? This can't be! Fixed! :p
– Arnauld
Dec 11 at 12:04
Wouldn't
n=>n<1?0:n.toString(2)-64
perform the same?– Ismael Miguel
Dec 10 at 12:59
Wouldn't
n=>n<1?0:n.toString(2)-64
perform the same?– Ismael Miguel
Dec 10 at 12:59
@IsmaelMiguel I suppose you meant
n=>n<1?0:n.toString(2).length-64
, but that would not work anyway. This would, I think.– Arnauld
Dec 10 at 13:28
@IsmaelMiguel I suppose you meant
n=>n<1?0:n.toString(2).length-64
, but that would not work anyway. This would, I think.– Arnauld
Dec 10 at 13:28
1
1
@IsmaelMiguel No worries. :) It's indeed possible to have the
.toString()
approach working, but we still need a BigInt literal as input. Otherwise, we only have 52 bits of mantissa, leading to invalid results when precision is lost.– Arnauld
Dec 10 at 13:48
@IsmaelMiguel No worries. :) It's indeed possible to have the
.toString()
approach working, but we still need a BigInt literal as input. Otherwise, we only have 52 bits of mantissa, leading to invalid results when precision is lost.– Arnauld
Dec 10 at 13:48
1
1
The fact that the BigInt suffix is the same character as your parameter is very confusing...
– Neil
Dec 11 at 9:25
The fact that the BigInt suffix is the same character as your parameter is very confusing...
– Neil
Dec 11 at 9:25
1
1
@Neil Unreadable code on PPCG?? This can't be! Fixed! :p
– Arnauld
Dec 11 at 12:04
@Neil Unreadable code on PPCG?? This can't be! Fixed! :p
– Arnauld
Dec 11 at 12:04
|
show 1 more comment
05AB1E, 10 9 bytes
·bg65αsd*
I/O are both integers
Try it online or verify all test cases.
Explanation:
· # 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
add a comment |
05AB1E, 10 9 bytes
·bg65αsd*
I/O are both integers
Try it online or verify all test cases.
Explanation:
· # 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
add a comment |
05AB1E, 10 9 bytes
·bg65αsd*
I/O are both integers
Try it online or verify all test cases.
Explanation:
· # 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
05AB1E, 10 9 bytes
·bg65αsd*
I/O are both integers
Try it online or verify all test cases.
Explanation:
· # 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
edited Dec 10 at 10:25
answered Dec 10 at 10:14
Kevin Cruijssen
35.6k554186
35.6k554186
add a comment |
add a comment |
APL+WIN, 34 bytes
+/×=(0>n),(63⍴2)⊤((2*63)××n)+n←⎕
Explanation:
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
+/×= Identify zeros, isolate first contiguous group and sum if first element is zero
add a comment |
APL+WIN, 34 bytes
+/×=(0>n),(63⍴2)⊤((2*63)××n)+n←⎕
Explanation:
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
+/×= Identify zeros, isolate first contiguous group and sum if first element is zero
add a comment |
APL+WIN, 34 bytes
+/×=(0>n),(63⍴2)⊤((2*63)××n)+n←⎕
Explanation:
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
+/×= Identify zeros, isolate first contiguous group and sum if first element is zero
APL+WIN, 34 bytes
+/×=(0>n),(63⍴2)⊤((2*63)××n)+n←⎕
Explanation:
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
+/×= Identify zeros, isolate first contiguous group and sum if first element is zero
edited Dec 10 at 11:11
answered Dec 10 at 11:03
Graham
2,24678
2,24678
add a comment |
add a comment |
Haskell, 56 bytes
Thanks xnor for spotting a mistake!
f n|n<0=0|1>0=sum.fst.span(>0)$mapM(pure[1,0])[1..64]!!n
Might allocate quite a lot of memory, try it online!
Maybe you want to test it with a smaller constant: Try 8-bit!
Explanation
Instead of using mapM(pure[0,1])[1..64]
to convert the input to binary, we'll use mapM(pure[1,0])[1..64]
which essentially generates the inverted strings $\{0,1\}^{64}$ in lexicographic order. So we can just sum the $1$s-prefix by using sum.fst.span(>0)
.
add a comment |
Haskell, 56 bytes
Thanks xnor for spotting a mistake!
f n|n<0=0|1>0=sum.fst.span(>0)$mapM(pure[1,0])[1..64]!!n
Might allocate quite a lot of memory, try it online!
Maybe you want to test it with a smaller constant: Try 8-bit!
Explanation
Instead of using mapM(pure[0,1])[1..64]
to convert the input to binary, we'll use mapM(pure[1,0])[1..64]
which essentially generates the inverted strings $\{0,1\}^{64}$ in lexicographic order. So we can just sum the $1$s-prefix by using sum.fst.span(>0)
.
add a comment |
Haskell, 56 bytes
Thanks xnor for spotting a mistake!
f n|n<0=0|1>0=sum.fst.span(>0)$mapM(pure[1,0])[1..64]!!n
Might allocate quite a lot of memory, try it online!
Maybe you want to test it with a smaller constant: Try 8-bit!
Explanation
Instead of using mapM(pure[0,1])[1..64]
to convert the input to binary, we'll use mapM(pure[1,0])[1..64]
which essentially generates the inverted strings $\{0,1\}^{64}$ in lexicographic order. So we can just sum the $1$s-prefix by using sum.fst.span(>0)
.
Haskell, 56 bytes
Thanks xnor for spotting a mistake!
f n|n<0=0|1>0=sum.fst.span(>0)$mapM(pure[1,0])[1..64]!!n
Might allocate quite a lot of memory, try it online!
Maybe you want to test it with a smaller constant: Try 8-bit!
Explanation
Instead of using mapM(pure[0,1])[1..64]
to convert the input to binary, we'll use mapM(pure[1,0])[1..64]
which essentially generates the inverted strings $\{0,1\}^{64}$ in lexicographic order. So we can just sum the $1$s-prefix by using sum.fst.span(>0)
.
edited Dec 10 at 14:14
answered Dec 10 at 0:59
BMO
11.3k22185
11.3k22185
add a comment |
add a comment |
Ruby, 22 bytes
->n{/[^0]/=~"%064b"%n}
Try it online!
add a comment |
Ruby, 22 bytes
->n{/[^0]/=~"%064b"%n}
Try it online!
add a comment |
Ruby, 22 bytes
->n{/[^0]/=~"%064b"%n}
Try it online!
Ruby, 22 bytes
->n{/[^0]/=~"%064b"%n}
Try it online!
answered Dec 10 at 21:16
G B
7,6861328
7,6861328
add a comment |
add a comment |
C# (Visual C# Interactive Compiler), 42 bytes
x=>x!=0?64-Convert.ToString(x,2).Length:64
Try it online!
C# (Visual C# Interactive Compiler), 31 bytes
int c(long x)=>x<0?0:c(x-~x)+1;
Even shorter, based off of @l4m2's C (gcc) answer.
Never knew that you could declare functions like that, thanks @Dana!
Try it online!
1
I think this is valid? tio.run/##ZZA/…
– dana
Dec 11 at 13:17
add a comment |
C# (Visual C# Interactive Compiler), 42 bytes
x=>x!=0?64-Convert.ToString(x,2).Length:64
Try it online!
C# (Visual C# Interactive Compiler), 31 bytes
int c(long x)=>x<0?0:c(x-~x)+1;
Even shorter, based off of @l4m2's C (gcc) answer.
Never knew that you could declare functions like that, thanks @Dana!
Try it online!
1
I think this is valid? tio.run/##ZZA/…
– dana
Dec 11 at 13:17
add a comment |
C# (Visual C# Interactive Compiler), 42 bytes
x=>x!=0?64-Convert.ToString(x,2).Length:64
Try it online!
C# (Visual C# Interactive Compiler), 31 bytes
int c(long x)=>x<0?0:c(x-~x)+1;
Even shorter, based off of @l4m2's C (gcc) answer.
Never knew that you could declare functions like that, thanks @Dana!
Try it online!
C# (Visual C# Interactive Compiler), 42 bytes
x=>x!=0?64-Convert.ToString(x,2).Length:64
Try it online!
C# (Visual C# Interactive Compiler), 31 bytes
int c(long x)=>x<0?0:c(x-~x)+1;
Even shorter, based off of @l4m2's C (gcc) answer.
Never knew that you could declare functions like that, thanks @Dana!
Try it online!
edited Dec 11 at 14:44
answered Dec 11 at 5:40
Embodiment of Ignorance
24711
24711
1
I think this is valid? tio.run/##ZZA/…
– dana
Dec 11 at 13:17
add a comment |
1
I think this is valid? tio.run/##ZZA/…
– dana
Dec 11 at 13:17
1
1
I think this is valid? tio.run/##ZZA/…
– dana
Dec 11 at 13:17
I think this is valid? tio.run/##ZZA/…
– dana
Dec 11 at 13:17
add a comment |
Jelly, 10 9 bytes
-1 thanks to a neat trick by Erik the Outgolfer (is-non-negative is now simply AƑ
)
ḤBL65_×AƑ
A monadic Link accepting an integer (within range) which yields an integer.
Try it online! Or see the test-suite.
The 10 was ḤBL65_ɓ>-×
Here is another 10 byte solution, which I like since it says it is "BOSS"...
BoṠS»-~%65
Test-suite here
...BoṠS63r0¤i
, BoṠS63ŻṚ¤i
, or BoṠS64ḶṚ¤i
would also work.
Another 10 byter (from Dennis) is æ»64ḶṚ¤Äċ0
(again æ»63r0¤Äċ0
and æ»63ŻṚ¤Äċ0
will also work)
9 bytes
– Erik the Outgolfer
Dec 11 at 18:18
@EriktheOutgolfer I thought to myself "there must be a golfier way to multiply by isNonNegative" and didn't think of theƑ
quick at all, very nice work!
– Jonathan Allan
Dec 11 at 19:11
1
Actually, I've been theorizing aboutAƑ
for quite some while now. Be warned that it doesn't vectorize! ;-) It's actually "flatten and then check if all elements are nonnegative".
– Erik the Outgolfer
Dec 11 at 19:14
add a comment |
Jelly, 10 9 bytes
-1 thanks to a neat trick by Erik the Outgolfer (is-non-negative is now simply AƑ
)
ḤBL65_×AƑ
A monadic Link accepting an integer (within range) which yields an integer.
Try it online! Or see the test-suite.
The 10 was ḤBL65_ɓ>-×
Here is another 10 byte solution, which I like since it says it is "BOSS"...
BoṠS»-~%65
Test-suite here
...BoṠS63r0¤i
, BoṠS63ŻṚ¤i
, or BoṠS64ḶṚ¤i
would also work.
Another 10 byter (from Dennis) is æ»64ḶṚ¤Äċ0
(again æ»63r0¤Äċ0
and æ»63ŻṚ¤Äċ0
will also work)
9 bytes
– Erik the Outgolfer
Dec 11 at 18:18
@EriktheOutgolfer I thought to myself "there must be a golfier way to multiply by isNonNegative" and didn't think of theƑ
quick at all, very nice work!
– Jonathan Allan
Dec 11 at 19:11
1
Actually, I've been theorizing aboutAƑ
for quite some while now. Be warned that it doesn't vectorize! ;-) It's actually "flatten and then check if all elements are nonnegative".
– Erik the Outgolfer
Dec 11 at 19:14
add a comment |
Jelly, 10 9 bytes
-1 thanks to a neat trick by Erik the Outgolfer (is-non-negative is now simply AƑ
)
ḤBL65_×AƑ
A monadic Link accepting an integer (within range) which yields an integer.
Try it online! Or see the test-suite.
The 10 was ḤBL65_ɓ>-×
Here is another 10 byte solution, which I like since it says it is "BOSS"...
BoṠS»-~%65
Test-suite here
...BoṠS63r0¤i
, BoṠS63ŻṚ¤i
, or BoṠS64ḶṚ¤i
would also work.
Another 10 byter (from Dennis) is æ»64ḶṚ¤Äċ0
(again æ»63r0¤Äċ0
and æ»63ŻṚ¤Äċ0
will also work)
Jelly, 10 9 bytes
-1 thanks to a neat trick by Erik the Outgolfer (is-non-negative is now simply AƑ
)
ḤBL65_×AƑ
A monadic Link accepting an integer (within range) which yields an integer.
Try it online! Or see the test-suite.
The 10 was ḤBL65_ɓ>-×
Here is another 10 byte solution, which I like since it says it is "BOSS"...
BoṠS»-~%65
Test-suite here
...BoṠS63r0¤i
, BoṠS63ŻṚ¤i
, or BoṠS64ḶṚ¤i
would also work.
Another 10 byter (from Dennis) is æ»64ḶṚ¤Äċ0
(again æ»63r0¤Äċ0
and æ»63ŻṚ¤Äċ0
will also work)
edited Dec 11 at 19:10
answered Dec 10 at 0:09
Jonathan Allan
50.7k534165
50.7k534165
9 bytes
– Erik the Outgolfer
Dec 11 at 18:18
@EriktheOutgolfer I thought to myself "there must be a golfier way to multiply by isNonNegative" and didn't think of theƑ
quick at all, very nice work!
– Jonathan Allan
Dec 11 at 19:11
1
Actually, I've been theorizing aboutAƑ
for quite some while now. Be warned that it doesn't vectorize! ;-) It's actually "flatten and then check if all elements are nonnegative".
– Erik the Outgolfer
Dec 11 at 19:14
add a comment |
9 bytes
– Erik the Outgolfer
Dec 11 at 18:18
@EriktheOutgolfer I thought to myself "there must be a golfier way to multiply by isNonNegative" and didn't think of theƑ
quick at all, very nice work!
– Jonathan Allan
Dec 11 at 19:11
1
Actually, I've been theorizing aboutAƑ
for quite some while now. Be warned that it doesn't vectorize! ;-) It's actually "flatten and then check if all elements are nonnegative".
– Erik the Outgolfer
Dec 11 at 19:14
9 bytes
– Erik the Outgolfer
Dec 11 at 18:18
9 bytes
– Erik the Outgolfer
Dec 11 at 18:18
@EriktheOutgolfer I thought to myself "there must be a golfier way to multiply by isNonNegative" and didn't think of the
Ƒ
quick at all, very nice work!– Jonathan Allan
Dec 11 at 19:11
@EriktheOutgolfer I thought to myself "there must be a golfier way to multiply by isNonNegative" and didn't think of the
Ƒ
quick at all, very nice work!– Jonathan Allan
Dec 11 at 19:11
1
1
Actually, I've been theorizing about
AƑ
for quite some while now. Be warned that it doesn't vectorize! ;-) It's actually "flatten and then check if all elements are nonnegative".– Erik the Outgolfer
Dec 11 at 19:14
Actually, I've been theorizing about
AƑ
for quite some while now. Be warned that it doesn't vectorize! ;-) It's actually "flatten and then check if all elements are nonnegative".– Erik the Outgolfer
Dec 11 at 19:14
add a comment |
Powershell, 51 bytes
param([long]$n)for(;$n-shl$i++-gt0){}($i,65)[!$n]-1
Test script:
$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"
}
Output:
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
add a comment |
Powershell, 51 bytes
param([long]$n)for(;$n-shl$i++-gt0){}($i,65)[!$n]-1
Test script:
$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"
}
Output:
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
add a comment |
Powershell, 51 bytes
param([long]$n)for(;$n-shl$i++-gt0){}($i,65)[!$n]-1
Test script:
$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"
}
Output:
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
Powershell, 51 bytes
param([long]$n)for(;$n-shl$i++-gt0){}($i,65)[!$n]-1
Test script:
$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"
}
Output:
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
answered Dec 10 at 7:39
mazzy
2,0851315
2,0851315
add a comment |
add a comment |
Java 8, 38 bytes
int f(long n){return n<0?0:f(n-~n)+1;}
Input as long
(64-bit integer), output as int
(32-bit integer).
Port of @l4m2's C (gcc) answer.
Try it online.
Explanation:
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
EDIT: Can be 26 bytes by using the builtin Long::numberOfLeadingZeros
as displayed in @lukeg's Java 8 answer.
add a comment |
Java 8, 38 bytes
int f(long n){return n<0?0:f(n-~n)+1;}
Input as long
(64-bit integer), output as int
(32-bit integer).
Port of @l4m2's C (gcc) answer.
Try it online.
Explanation:
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
EDIT: Can be 26 bytes by using the builtin Long::numberOfLeadingZeros
as displayed in @lukeg's Java 8 answer.
add a comment |
Java 8, 38 bytes
int f(long n){return n<0?0:f(n-~n)+1;}
Input as long
(64-bit integer), output as int
(32-bit integer).
Port of @l4m2's C (gcc) answer.
Try it online.
Explanation:
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
EDIT: Can be 26 bytes by using the builtin Long::numberOfLeadingZeros
as displayed in @lukeg's Java 8 answer.
Java 8, 38 bytes
int f(long n){return n<0?0:f(n-~n)+1;}
Input as long
(64-bit integer), output as int
(32-bit integer).
Port of @l4m2's C (gcc) answer.
Try it online.
Explanation:
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
EDIT: Can be 26 bytes by using the builtin Long::numberOfLeadingZeros
as displayed in @lukeg's Java 8 answer.
edited Dec 10 at 10:48
answered Dec 10 at 10:35
Kevin Cruijssen
35.6k554186
35.6k554186
add a comment |
add a comment |
Perl 5, 37 bytes
sub{sprintf("%064b",@_)=~/^0*/;$+[0]}
Try it online!
Or this 46 bytes if the "stringification" is not allowed: sub z
sub{my$i=0;$_[0]>>64-$_?last:$i++for 1..64;$i}
s/length$&/$+[0]/
(-3 bytes) ;)
– Dada
Dec 10 at 12:59
IMO, you're not allowed to remove thesub
keyword from answers containing Perl 5 functions.
– nwellnhof
Dec 10 at 14:36
I've seen whats similar to removingsub
in answers for other languages, perl6, powershell and more.
– Kjetil S.
Dec 10 at 14:58
In Perl6, I think you don't needsub{}
to make a (anonymous?) sub, which explain why it's omitted from Perl6 answers. I agree with @nwellnhof that you shouldn't be allowed to removesub
. (when I was still active, like a year ago or so, that was the rule)
– Dada
Dec 10 at 15:03
changed now. And included$+[0]
.
– Kjetil S.
Dec 10 at 15:10
add a comment |
Perl 5, 37 bytes
sub{sprintf("%064b",@_)=~/^0*/;$+[0]}
Try it online!
Or this 46 bytes if the "stringification" is not allowed: sub z
sub{my$i=0;$_[0]>>64-$_?last:$i++for 1..64;$i}
s/length$&/$+[0]/
(-3 bytes) ;)
– Dada
Dec 10 at 12:59
IMO, you're not allowed to remove thesub
keyword from answers containing Perl 5 functions.
– nwellnhof
Dec 10 at 14:36
I've seen whats similar to removingsub
in answers for other languages, perl6, powershell and more.
– Kjetil S.
Dec 10 at 14:58
In Perl6, I think you don't needsub{}
to make a (anonymous?) sub, which explain why it's omitted from Perl6 answers. I agree with @nwellnhof that you shouldn't be allowed to removesub
. (when I was still active, like a year ago or so, that was the rule)
– Dada
Dec 10 at 15:03
changed now. And included$+[0]
.
– Kjetil S.
Dec 10 at 15:10
add a comment |
Perl 5, 37 bytes
sub{sprintf("%064b",@_)=~/^0*/;$+[0]}
Try it online!
Or this 46 bytes if the "stringification" is not allowed: sub z
sub{my$i=0;$_[0]>>64-$_?last:$i++for 1..64;$i}
Perl 5, 37 bytes
sub{sprintf("%064b",@_)=~/^0*/;$+[0]}
Try it online!
Or this 46 bytes if the "stringification" is not allowed: sub z
sub{my$i=0;$_[0]>>64-$_?last:$i++for 1..64;$i}
edited Dec 10 at 15:09
answered Dec 10 at 12:45
Kjetil S.
56915
56915
s/length$&/$+[0]/
(-3 bytes) ;)
– Dada
Dec 10 at 12:59
IMO, you're not allowed to remove thesub
keyword from answers containing Perl 5 functions.
– nwellnhof
Dec 10 at 14:36
I've seen whats similar to removingsub
in answers for other languages, perl6, powershell and more.
– Kjetil S.
Dec 10 at 14:58
In Perl6, I think you don't needsub{}
to make a (anonymous?) sub, which explain why it's omitted from Perl6 answers. I agree with @nwellnhof that you shouldn't be allowed to removesub
. (when I was still active, like a year ago or so, that was the rule)
– Dada
Dec 10 at 15:03
changed now. And included$+[0]
.
– Kjetil S.
Dec 10 at 15:10
add a comment |
s/length$&/$+[0]/
(-3 bytes) ;)
– Dada
Dec 10 at 12:59
IMO, you're not allowed to remove thesub
keyword from answers containing Perl 5 functions.
– nwellnhof
Dec 10 at 14:36
I've seen whats similar to removingsub
in answers for other languages, perl6, powershell and more.
– Kjetil S.
Dec 10 at 14:58
In Perl6, I think you don't needsub{}
to make a (anonymous?) sub, which explain why it's omitted from Perl6 answers. I agree with @nwellnhof that you shouldn't be allowed to removesub
. (when I was still active, like a year ago or so, that was the rule)
– Dada
Dec 10 at 15:03
changed now. And included$+[0]
.
– Kjetil S.
Dec 10 at 15:10
s/length$&/$+[0]/
(-3 bytes) ;)– Dada
Dec 10 at 12:59
s/length$&/$+[0]/
(-3 bytes) ;)– Dada
Dec 10 at 12:59
IMO, you're not allowed to remove the
sub
keyword from answers containing Perl 5 functions.– nwellnhof
Dec 10 at 14:36
IMO, you're not allowed to remove the
sub
keyword from answers containing Perl 5 functions.– nwellnhof
Dec 10 at 14:36
I've seen whats similar to removing
sub
in answers for other languages, perl6, powershell and more.– Kjetil S.
Dec 10 at 14:58
I've seen whats similar to removing
sub
in answers for other languages, perl6, powershell and more.– Kjetil S.
Dec 10 at 14:58
In Perl6, I think you don't need
sub{}
to make a (anonymous?) sub, which explain why it's omitted from Perl6 answers. I agree with @nwellnhof that you shouldn't be allowed to remove sub
. (when I was still active, like a year ago or so, that was the rule)– Dada
Dec 10 at 15:03
In Perl6, I think you don't need
sub{}
to make a (anonymous?) sub, which explain why it's omitted from Perl6 answers. I agree with @nwellnhof that you shouldn't be allowed to remove sub
. (when I was still active, like a year ago or so, that was the rule)– Dada
Dec 10 at 15:03
changed now. And included
$+[0]
.– Kjetil S.
Dec 10 at 15:10
changed now. And included
$+[0]
.– Kjetil S.
Dec 10 at 15:10
add a comment |
Swift (on a 64-bit platform), 41 bytes
Declares a closure called f
which accepts and returns an Int
. This solution only works correctly 64-bit platforms, where Int
is typealias
ed to Int64
. (On a 32-bit platform, Int64
can be used explicitly for the closure’s parameter type, adding 2 bytes.)
let f:(Int)->Int={$0.leadingZeroBitCount}
In Swift, even the fundamental integer type is an ordinary object declared in the standard library. This means Int
can have methods and properties, such as leadingZeroBitCount
(which is required on all types conforming to the standard library’s FixedWidthInteger
protocol).
add a comment |
Swift (on a 64-bit platform), 41 bytes
Declares a closure called f
which accepts and returns an Int
. This solution only works correctly 64-bit platforms, where Int
is typealias
ed to Int64
. (On a 32-bit platform, Int64
can be used explicitly for the closure’s parameter type, adding 2 bytes.)
let f:(Int)->Int={$0.leadingZeroBitCount}
In Swift, even the fundamental integer type is an ordinary object declared in the standard library. This means Int
can have methods and properties, such as leadingZeroBitCount
(which is required on all types conforming to the standard library’s FixedWidthInteger
protocol).
add a comment |
Swift (on a 64-bit platform), 41 bytes
Declares a closure called f
which accepts and returns an Int
. This solution only works correctly 64-bit platforms, where Int
is typealias
ed to Int64
. (On a 32-bit platform, Int64
can be used explicitly for the closure’s parameter type, adding 2 bytes.)
let f:(Int)->Int={$0.leadingZeroBitCount}
In Swift, even the fundamental integer type is an ordinary object declared in the standard library. This means Int
can have methods and properties, such as leadingZeroBitCount
(which is required on all types conforming to the standard library’s FixedWidthInteger
protocol).
Swift (on a 64-bit platform), 41 bytes
Declares a closure called f
which accepts and returns an Int
. This solution only works correctly 64-bit platforms, where Int
is typealias
ed to Int64
. (On a 32-bit platform, Int64
can be used explicitly for the closure’s parameter type, adding 2 bytes.)
let f:(Int)->Int={$0.leadingZeroBitCount}
In Swift, even the fundamental integer type is an ordinary object declared in the standard library. This means Int
can have methods and properties, such as leadingZeroBitCount
(which is required on all types conforming to the standard library’s FixedWidthInteger
protocol).
edited Dec 10 at 17:12
answered Dec 10 at 5:27
NobodyNada
510410
510410
add a comment |
add a comment |
Clean, 103 bytes
Uses the same "builtin" as ceilingcat's answer.
f::!Int->Int
f _=code {
instruction 243
instruction 72
instruction 15
instruction 189
instruction 192
}
Try it online!
Clean, 58 bytes
import StdEnv
$0=64
$i=until(e=(2^63>>e)bitand i<>0)inc 0
Try it online!
add a comment |
Clean, 103 bytes
Uses the same "builtin" as ceilingcat's answer.
f::!Int->Int
f _=code {
instruction 243
instruction 72
instruction 15
instruction 189
instruction 192
}
Try it online!
Clean, 58 bytes
import StdEnv
$0=64
$i=until(e=(2^63>>e)bitand i<>0)inc 0
Try it online!
add a comment |
Clean, 103 bytes
Uses the same "builtin" as ceilingcat's answer.
f::!Int->Int
f _=code {
instruction 243
instruction 72
instruction 15
instruction 189
instruction 192
}
Try it online!
Clean, 58 bytes
import StdEnv
$0=64
$i=until(e=(2^63>>e)bitand i<>0)inc 0
Try it online!
Clean, 103 bytes
Uses the same "builtin" as ceilingcat's answer.
f::!Int->Int
f _=code {
instruction 243
instruction 72
instruction 15
instruction 189
instruction 192
}
Try it online!
Clean, 58 bytes
import StdEnv
$0=64
$i=until(e=(2^63>>e)bitand i<>0)inc 0
Try it online!
edited Dec 10 at 4:03
answered Dec 10 at 1:31
Οurous
6,42311033
6,42311033
add a comment |
add a comment |
Stax, 10 bytes
în»╧3(∞┼⌠g
Run and debug it
It's a port of Kevin's 05AB1E solution.
add a comment |
Stax, 10 bytes
în»╧3(∞┼⌠g
Run and debug it
It's a port of Kevin's 05AB1E solution.
add a comment |
Stax, 10 bytes
în»╧3(∞┼⌠g
Run and debug it
It's a port of Kevin's 05AB1E solution.
Stax, 10 bytes
în»╧3(∞┼⌠g
Run and debug it
It's a port of Kevin's 05AB1E solution.
answered Dec 10 at 20:53
recursive
5,0041221
5,0041221
add a comment |
add a comment |
Perl 5 -p
, 42 bytes
1while$_>0&&2**++$a-1<$_;$_=0|$_>=0&&64-$a
Try it online!
Longer than a bitstring based solution, but a decent math based solution.
Doesn't really work if I'm not mistaken
– Dada
Dec 11 at 12:23
@Dada I see that there are a few cases where the floating point division doesn't quite work out properly. I put in anint
call that should solve the issue.
– Xcali
Dec 11 at 15:55
Sorry, I failed my copy-past it would seem. This is what I wanted to send ;)
– Dada
Dec 11 at 17:36
add a comment |
Perl 5 -p
, 42 bytes
1while$_>0&&2**++$a-1<$_;$_=0|$_>=0&&64-$a
Try it online!
Longer than a bitstring based solution, but a decent math based solution.
Doesn't really work if I'm not mistaken
– Dada
Dec 11 at 12:23
@Dada I see that there are a few cases where the floating point division doesn't quite work out properly. I put in anint
call that should solve the issue.
– Xcali
Dec 11 at 15:55
Sorry, I failed my copy-past it would seem. This is what I wanted to send ;)
– Dada
Dec 11 at 17:36
add a comment |
Perl 5 -p
, 42 bytes
1while$_>0&&2**++$a-1<$_;$_=0|$_>=0&&64-$a
Try it online!
Longer than a bitstring based solution, but a decent math based solution.
Perl 5 -p
, 42 bytes
1while$_>0&&2**++$a-1<$_;$_=0|$_>=0&&64-$a
Try it online!
Longer than a bitstring based solution, but a decent math based solution.
edited Dec 11 at 19:00
answered Dec 11 at 1:01
Xcali
5,168520
5,168520
Doesn't really work if I'm not mistaken
– Dada
Dec 11 at 12:23
@Dada I see that there are a few cases where the floating point division doesn't quite work out properly. I put in anint
call that should solve the issue.
– Xcali
Dec 11 at 15:55
Sorry, I failed my copy-past it would seem. This is what I wanted to send ;)
– Dada
Dec 11 at 17:36
add a comment |
Doesn't really work if I'm not mistaken
– Dada
Dec 11 at 12:23
@Dada I see that there are a few cases where the floating point division doesn't quite work out properly. I put in anint
call that should solve the issue.
– Xcali
Dec 11 at 15:55
Sorry, I failed my copy-past it would seem. This is what I wanted to send ;)
– Dada
Dec 11 at 17:36
Doesn't really work if I'm not mistaken
– Dada
Dec 11 at 12:23
Doesn't really work if I'm not mistaken
– Dada
Dec 11 at 12:23
@Dada I see that there are a few cases where the floating point division doesn't quite work out properly. I put in an
int
call that should solve the issue.– Xcali
Dec 11 at 15:55
@Dada I see that there are a few cases where the floating point division doesn't quite work out properly. I put in an
int
call that should solve the issue.– Xcali
Dec 11 at 15:55
Sorry, I failed my copy-past it would seem. This is what I wanted to send ;)
– Dada
Dec 11 at 17:36
Sorry, I failed my copy-past it would seem. This is what I wanted to send ;)
– Dada
Dec 11 at 17:36
add a comment |
APL(NARS), 15 chars, 30 bytes
{¯1+1⍳⍨⍵⊤⍨64⍴2}
test for few numbers for see how to use:
f←{¯1+1⍳⍨⍵⊤⍨64⍴2}
f ¯9223372036854775808
0
f 9223372036854775807
1
add a comment |
APL(NARS), 15 chars, 30 bytes
{¯1+1⍳⍨⍵⊤⍨64⍴2}
test for few numbers for see how to use:
f←{¯1+1⍳⍨⍵⊤⍨64⍴2}
f ¯9223372036854775808
0
f 9223372036854775807
1
add a comment |
APL(NARS), 15 chars, 30 bytes
{¯1+1⍳⍨⍵⊤⍨64⍴2}
test for few numbers for see how to use:
f←{¯1+1⍳⍨⍵⊤⍨64⍴2}
f ¯9223372036854775808
0
f 9223372036854775807
1
APL(NARS), 15 chars, 30 bytes
{¯1+1⍳⍨⍵⊤⍨64⍴2}
test for few numbers for see how to use:
f←{¯1+1⍳⍨⍵⊤⍨64⍴2}
f ¯9223372036854775808
0
f 9223372036854775807
1
answered Dec 11 at 19:10
RosLuP
1,806514
1,806514
add a comment |
add a comment |
K (ngn/k), 6 bytes
64-#2
Try it online!
2
encode the argument in binary
#
length
64-
subtract from 64
# = length
... looks string based
– Titus
Dec 13 at 14:37
2
@Titus2
gives a list of integers and#
finds its length. no strings are involved here.
– ngn
Dec 13 at 15:38
add a comment |
K (ngn/k), 6 bytes
64-#2
Try it online!
2
encode the argument in binary
#
length
64-
subtract from 64
# = length
... looks string based
– Titus
Dec 13 at 14:37
2
@Titus2
gives a list of integers and#
finds its length. no strings are involved here.
– ngn
Dec 13 at 15:38
add a comment |
K (ngn/k), 6 bytes
64-#2
Try it online!
2
encode the argument in binary
#
length
64-
subtract from 64
K (ngn/k), 6 bytes
64-#2
Try it online!
2
encode the argument in binary
#
length
64-
subtract from 64
answered Dec 13 at 11:22
ngn
6,94112559
6,94112559
# = length
... looks string based
– Titus
Dec 13 at 14:37
2
@Titus2
gives a list of integers and#
finds its length. no strings are involved here.
– ngn
Dec 13 at 15:38
add a comment |
# = length
... looks string based
– Titus
Dec 13 at 14:37
2
@Titus2
gives a list of integers and#
finds its length. no strings are involved here.
– ngn
Dec 13 at 15:38
# = length
... looks string based– Titus
Dec 13 at 14:37
# = length
... looks string based– Titus
Dec 13 at 14:37
2
2
@Titus
2
gives a list of integers and #
finds its length. no strings are involved here.– ngn
Dec 13 at 15:38
@Titus
2
gives a list of integers and #
finds its length. no strings are involved here.– ngn
Dec 13 at 15:38
add a comment |
PHP, 50 46 bytes
for(;0<$n=&$argn;$n>>=1)$i++;echo$n<0?0:64-$i;
Run as pipe with -R
or try it online,
<?=$argn<0?0:0|64-log($argn+1,2);
has rounding issues; so I took the long way.
add a comment |
PHP, 50 46 bytes
for(;0<$n=&$argn;$n>>=1)$i++;echo$n<0?0:64-$i;
Run as pipe with -R
or try it online,
<?=$argn<0?0:0|64-log($argn+1,2);
has rounding issues; so I took the long way.
add a comment |
PHP, 50 46 bytes
for(;0<$n=&$argn;$n>>=1)$i++;echo$n<0?0:64-$i;
Run as pipe with -R
or try it online,
<?=$argn<0?0:0|64-log($argn+1,2);
has rounding issues; so I took the long way.
PHP, 50 46 bytes
for(;0<$n=&$argn;$n>>=1)$i++;echo$n<0?0:64-$i;
Run as pipe with -R
or try it online,
<?=$argn<0?0:0|64-log($argn+1,2);
has rounding issues; so I took the long way.
edited Dec 13 at 15:20
answered Dec 13 at 15:12
Titus
13k11238
13k11238
add a comment |
add a comment |
Wolfram Language (Mathematica), 41 bytes
The formula for positive numbers is just 63-Floor@Log2@#&
. Replacement rules are used for the special cases of zero and negative input.
The input need not be a 64-bit signed integer. This will effectively take the floor of the input to turn it into an integer. If you input a number outside of the normal bounds for a 64-bit integer, it will tell return a negative number indicating how many more bits would be needed to store this integer.
63-Floor@Log2[#/.{_?(#<0&):>2^63,0:>.5}]&
Try it online!
@LegionMammal978's solution is quite a bit shorter at 28 bytes. The input must be an integer. Per the documentation: "BitLength[n]
is effectively an efficient version of Floor[Log[2,n]]+1
. " It automatically handles the case of zero correctly reporting 0
rather than -∞
.
Wolfram Language (Mathematica), 28 bytes
Boole[#>=0](64-BitLength@#)&
Try it online!
1
Boole[#>=0](64-BitLength@#)&
is a good bit shorter at 28 bytes. It uses the same basic concept as yours, but appliesBitLength
andBoole
.
– LegionMammal978
Dec 12 at 2:13
I totally forgot about BitLength!
– Kelly Lowder
Dec 14 at 2:29
add a comment |
Wolfram Language (Mathematica), 41 bytes
The formula for positive numbers is just 63-Floor@Log2@#&
. Replacement rules are used for the special cases of zero and negative input.
The input need not be a 64-bit signed integer. This will effectively take the floor of the input to turn it into an integer. If you input a number outside of the normal bounds for a 64-bit integer, it will tell return a negative number indicating how many more bits would be needed to store this integer.
63-Floor@Log2[#/.{_?(#<0&):>2^63,0:>.5}]&
Try it online!
@LegionMammal978's solution is quite a bit shorter at 28 bytes. The input must be an integer. Per the documentation: "BitLength[n]
is effectively an efficient version of Floor[Log[2,n]]+1
. " It automatically handles the case of zero correctly reporting 0
rather than -∞
.
Wolfram Language (Mathematica), 28 bytes
Boole[#>=0](64-BitLength@#)&
Try it online!
1
Boole[#>=0](64-BitLength@#)&
is a good bit shorter at 28 bytes. It uses the same basic concept as yours, but appliesBitLength
andBoole
.
– LegionMammal978
Dec 12 at 2:13
I totally forgot about BitLength!
– Kelly Lowder
Dec 14 at 2:29
add a comment |
Wolfram Language (Mathematica), 41 bytes
The formula for positive numbers is just 63-Floor@Log2@#&
. Replacement rules are used for the special cases of zero and negative input.
The input need not be a 64-bit signed integer. This will effectively take the floor of the input to turn it into an integer. If you input a number outside of the normal bounds for a 64-bit integer, it will tell return a negative number indicating how many more bits would be needed to store this integer.
63-Floor@Log2[#/.{_?(#<0&):>2^63,0:>.5}]&
Try it online!
@LegionMammal978's solution is quite a bit shorter at 28 bytes. The input must be an integer. Per the documentation: "BitLength[n]
is effectively an efficient version of Floor[Log[2,n]]+1
. " It automatically handles the case of zero correctly reporting 0
rather than -∞
.
Wolfram Language (Mathematica), 28 bytes
Boole[#>=0](64-BitLength@#)&
Try it online!
Wolfram Language (Mathematica), 41 bytes
The formula for positive numbers is just 63-Floor@Log2@#&
. Replacement rules are used for the special cases of zero and negative input.
The input need not be a 64-bit signed integer. This will effectively take the floor of the input to turn it into an integer. If you input a number outside of the normal bounds for a 64-bit integer, it will tell return a negative number indicating how many more bits would be needed to store this integer.
63-Floor@Log2[#/.{_?(#<0&):>2^63,0:>.5}]&
Try it online!
@LegionMammal978's solution is quite a bit shorter at 28 bytes. The input must be an integer. Per the documentation: "BitLength[n]
is effectively an efficient version of Floor[Log[2,n]]+1
. " It automatically handles the case of zero correctly reporting 0
rather than -∞
.
Wolfram Language (Mathematica), 28 bytes
Boole[#>=0](64-BitLength@#)&
Try it online!
edited Dec 14 at 2:29
answered Dec 10 at 23:25
Kelly Lowder
2,998416
2,998416
1
Boole[#>=0](64-BitLength@#)&
is a good bit shorter at 28 bytes. It uses the same basic concept as yours, but appliesBitLength
andBoole
.
– LegionMammal978
Dec 12 at 2:13
I totally forgot about BitLength!
– Kelly Lowder
Dec 14 at 2:29
add a comment |
1
Boole[#>=0](64-BitLength@#)&
is a good bit shorter at 28 bytes. It uses the same basic concept as yours, but appliesBitLength
andBoole
.
– LegionMammal978
Dec 12 at 2:13
I totally forgot about BitLength!
– Kelly Lowder
Dec 14 at 2:29
1
1
Boole[#>=0](64-BitLength@#)&
is a good bit shorter at 28 bytes. It uses the same basic concept as yours, but applies BitLength
and Boole
.– LegionMammal978
Dec 12 at 2:13
Boole[#>=0](64-BitLength@#)&
is a good bit shorter at 28 bytes. It uses the same basic concept as yours, but applies BitLength
and Boole
.– LegionMammal978
Dec 12 at 2:13
I totally forgot about BitLength!
– Kelly Lowder
Dec 14 at 2:29
I totally forgot about BitLength!
– Kelly Lowder
Dec 14 at 2:29
add a comment |
Charcoal, 15 bytes
I⁻⁶⁴L↨﹪NX²¦⁶⁴¦²
Try it online! Link is to verbose version of code. Explanation:
L Length of
N Input as a number
﹪ Modulo
² Literal 2
X To the power
⁶⁴ Literal 64
↨ Converted to base
² Literal 2
⁻ Subtracted from
⁶⁴ Literal 64
I Cast to string
Implicitly print
The ¦
s serve to separate adjacent integer literals. Conveniently, Charcoal's arbitrary numeric base conversion converts 0
into an empty list, however for negative numbers it simply inverts the sign of each digit, so the number is converted to the equivalent unsigned 64-bit integer first.
add a comment |
Charcoal, 15 bytes
I⁻⁶⁴L↨﹪NX²¦⁶⁴¦²
Try it online! Link is to verbose version of code. Explanation:
L Length of
N Input as a number
﹪ Modulo
² Literal 2
X To the power
⁶⁴ Literal 64
↨ Converted to base
² Literal 2
⁻ Subtracted from
⁶⁴ Literal 64
I Cast to string
Implicitly print
The ¦
s serve to separate adjacent integer literals. Conveniently, Charcoal's arbitrary numeric base conversion converts 0
into an empty list, however for negative numbers it simply inverts the sign of each digit, so the number is converted to the equivalent unsigned 64-bit integer first.
add a comment |
Charcoal, 15 bytes
I⁻⁶⁴L↨﹪NX²¦⁶⁴¦²
Try it online! Link is to verbose version of code. Explanation:
L Length of
N Input as a number
﹪ Modulo
² Literal 2
X To the power
⁶⁴ Literal 64
↨ Converted to base
² Literal 2
⁻ Subtracted from
⁶⁴ Literal 64
I Cast to string
Implicitly print
The ¦
s serve to separate adjacent integer literals. Conveniently, Charcoal's arbitrary numeric base conversion converts 0
into an empty list, however for negative numbers it simply inverts the sign of each digit, so the number is converted to the equivalent unsigned 64-bit integer first.
Charcoal, 15 bytes
I⁻⁶⁴L↨﹪NX²¦⁶⁴¦²
Try it online! Link is to verbose version of code. Explanation:
L Length of
N Input as a number
﹪ Modulo
² Literal 2
X To the power
⁶⁴ Literal 64
↨ Converted to base
² Literal 2
⁻ Subtracted from
⁶⁴ Literal 64
I Cast to string
Implicitly print
The ¦
s serve to separate adjacent integer literals. Conveniently, Charcoal's arbitrary numeric base conversion converts 0
into an empty list, however for negative numbers it simply inverts the sign of each digit, so the number is converted to the equivalent unsigned 64-bit integer first.
answered Dec 11 at 9:51
Neil
79.3k744177
79.3k744177
add a comment |
add a comment |
Rust, 18 bytes
i64::leading_zeros
Try it online!
add a comment |
Rust, 18 bytes
i64::leading_zeros
Try it online!
add a comment |
Rust, 18 bytes
i64::leading_zeros
Try it online!
Rust, 18 bytes
i64::leading_zeros
Try it online!
answered Dec 12 at 8:28
Hannes Karppila
2,00421136
2,00421136
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f177271%2ffind-the-number-of-leading-zeroes-in-a-64-bit-integer%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
11
Welcome to PPCG! What's the reason behind "the input cannot be treated as string"? This disqualifies all languages that can't handle 64-bit integers and is unlikely to lead to more answers that take an integer, because this is the straightforward way when available anyway.
– Arnauld
Dec 9 at 23:26
1
Can we return
False
instead of0
?– Jo King
Dec 9 at 23:33
4
@Arnauld There are already similar questions here and on other sites that specifically call for string-based solutions, but nothing that opens the question to math and logical operations. My hope is to see a bunch of different approaches to this problem that are not already answered elsewhere. Should this be opened to string solutions as well to be all-inclusive?
– Dave
Dec 9 at 23:40
3
Several CPUs including x86 and ARM have specific instructions for this (x86 actually have several). I've always wondered why programming languages don't expose this feature since in most programming languages today you can't invoke assembly instructions.
– slebetman
Dec 10 at 5:43
1
@user202729 I think I worded this poorly: 'The output should be validated against the 64-bit signed integer representation of the number, regardless of language' What I mean by that is that this question defines the number of zeros as the number of zeros in a 64-bit signed integer. I guess I made that constraint to eliminate signed vs unsigned integers.
– Dave
Dec 11 at 0:26