Timeline for Counting the number of consecutive 1's in binary
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 27, 2019 at 21:14 | comment | added | Voo | Using strings to manipulate numbers strikes me as incredibly inelegant. | |
| Dec 27, 2019 at 9:14 | comment | added | Peter Cordes |
@Zchpyvr: Ah right, Anatolii's answer was what I was remembering: iterate x &= x << 1; until x becomes zero, counting the iterations. It's not O(1), just O(result), but doesn't involve any bit-scan.
|
|
| Dec 26, 2019 at 21:21 | comment | added | Anatolii | @Zchpyvr The author wasn't asking about the highest performance solution anyways. This one is good enough as it's easy to understand, it has a linear time complexity (in regard to binary digits) and the author also accepted it. | |
| Dec 26, 2019 at 20:57 | comment | added | Peter Cordes |
@Zchpyvr: I'd recommend posting your own answer with a focus on performance, where you'll have room to show a fast version and prove your points about what's faster for what kinds of input numbers (fits in 32 bits; huge; a few long runs of ones, alternating zeros and ones). I suspect that expanding a number into a list of base-2 digits at all is relatively slow, and I seem to recall a solution for this involving a bitwise trick. But maybe only in C where you don't have Python interpreter overhead, and maybe involving popcount or bitscan (__builtin_ctz() count trailing zeros)
|
|
| Dec 26, 2019 at 19:07 | comment | added | RomanPerekhrest | @Zchpyvr, Admitting faults is a strong human quality. | |
| Dec 26, 2019 at 19:06 | comment | added | Zchpyvr |
My comments about the other points remain valid, however. There are a lot of simple ways to improve this answer that are better in terms of readability and performance. Even using .split('0') is more performant and easier to read than your answer. But if you want to ignore me based on an error on my part about speed, then I understand. I just wanted to suggest some edits.
|
|
| Dec 26, 2019 at 19:01 | comment | added | Zchpyvr | My bad, I must've misread 'ns' as 'μs'. I apologize for that. | |
| Dec 26, 2019 at 10:11 | comment | added | Poutrathor | @RomanPerekhrest Oh :) I did not believe him (nor do I believe you, yet). I merely wrote a polite answer awaiting the time I could test it myself and asking "compared to" [which implementation] such an improvement was measured. For one, you tested only one number 188888889000. | |
| Dec 26, 2019 at 8:41 | comment | added | RomanPerekhrest | @Poutrathor, I would not believe in every comment saying 100x or 1000x speedups - it's better to check it out for yourself to find the truth. See the above comment with timings. Critical thinking is an advantage. | |
| Dec 26, 2019 at 8:37 | comment | added | RomanPerekhrest |
@Zchpyvr, Why telling people "fairy tails" about 100x speed improvement? Your approach is slower: In [56]: %timeit len(max(bin(18888889000)[2:].replace('0', ' ').split(), key=len)) 1.74 µs ± 160 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) - In [57]: %timeit len(max(re.split(r'0+', bin(18888889000)[2:]))) 4.26 µs ± 196 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
|
|
| Dec 26, 2019 at 6:51 | vote | accept | Kshitiz Koirala | ||
| Dec 25, 2019 at 23:42 | comment | added | Poutrathor | Compared to @roman 's answer? That's a nice improvement | |
| Dec 25, 2019 at 23:36 | comment | added | Zchpyvr | @Poutrathor My profiler gives me a 100x speed improvement. But I do agree with readability. | |
| Dec 25, 2019 at 22:07 | comment | added | Poutrathor |
using re: max(re.split(r'0+', bin(18888889)[2:])). >> it's harder to read. If no performance gain, code should aim for maximal readability. Code is a human machine interface after all
|
|
| Dec 25, 2019 at 17:00 | comment | added | Zchpyvr |
Or at least can we agree that key=len is not necessary?
|
|
| Dec 25, 2019 at 16:57 | comment | added | Zchpyvr |
Sure, although all the extra items are empty strings. Assuming the empty strings create extra overhead, what would you think of using re: max(re.split(r'0+', bin(18888889)[2:]))?
|
|
| Dec 25, 2019 at 16:45 | comment | added | RomanPerekhrest |
@Zchpyvr, I would not consider that as better approach. Consider this case: bin(18888889)[2:].split('0') that generates ['1', '', '1', '', '', '', '', '', '', '111', '', '', '1', '111', '', '1'] , a list of 16 items for further traversal. While the former approach returns a list of 6 items.
|
|
| Dec 25, 2019 at 16:20 | comment | added | Zchpyvr |
I know this is not meant to be codegolfed, but your return line can be written shorter as return len(max(bin_num.split('0')))
|
|
| Dec 25, 2019 at 9:01 | history | answered | RomanPerekhrest | CC BY-SA 4.0 |