18
3
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
14Welcome 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 – 2018-12-09T23:26:06.153
1Can we return
False
instead of0
? – Jo King – 2018-12-09T23:33:31.7574@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 – 2018-12-09T23:40:17.500
4Several 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 – 2018-12-10T05:43:42.973
It's 64 - log2.
– user202729 – 2018-12-10T13:30:10.130@user202729 For positive input. – Dennis – 2018-12-10T13:32:45.260
@Dave Unobservable requirements are discouraged, although it's ok to simply encourage using methods you want.
– user202729 – 2018-12-10T13:33:05.8871@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 – 2018-12-11T00:26:48.213
@slebetman I thought that built-ins were excluded as part of the default code golf rules, but I just saw that it's only a suggested rule.
I assume changing the requirements at this point is poor form, but I'll remember that in the future! – Dave – 2018-12-11T00:35:16.240
The equation for this is 64 if 0, 0 if -ve and 63-floor(log2(n)) otherwise – fəˈnɛtɪk – 2018-12-11T02:41:54.010
Don't "Do X without Y" – cat – 2018-12-11T22:28:26.037
1
@slebetman: many languages do have builtins for this, almost to the point where C and C++ are notable for their failure to portably expose modern CPU features like popcnt and bit-scan. (Especially given their use-case of low-overhead highly-optimized code). Most C compilers have their own incompatible and/or arch-specific intrinsics and builtins for this stuff. Rust is fantastic; all the primitive integer types have popcnt, bit-scan, rotate, endian, saturating add/sub, and wrapping vs. overflow-checked vs. non-overflowing add/sub/mul/div etc. https://doc.rust-lang.org/std/primitive.i32.html
– Peter Cordes – 2018-12-12T01:06:04.897