Timeline for Printing longest sequence of zeroes
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Feb 5, 2019 at 12:36 | history | suggested | One Lyner | CC BY-SA 4.0 |
Fixed the use of lowestOneBit and highestOneBit
|
| Feb 5, 2019 at 9:13 | review | Suggested edits | |||
| S Feb 5, 2019 at 12:36 | |||||
| Feb 5, 2019 at 9:02 | comment | added | One Lyner | Or change the way you use start and end in the loop. You can shift position instead of incrementing it, and use it directly as a bitmask. | |
| Feb 5, 2019 at 1:27 | comment | added | Reinstate Monica |
@OneLyner Good catch. I believe the answer should use Integer.numberOfLeadingZeros and Integer.numberOfTrailingZeros instead. Do you want to fix?
|
|
| Feb 4, 2019 at 23:44 | comment | added | One Lyner | There is a mistake here as lowestOneBit doesn't return the position of the lowest set bit, but "an int value with at most a single one-bit, in the position of the lowest-order ('rightmost') one-bit in the specified int value" (and similarly for highestOneBit). | |
| Jun 21, 2016 at 21:42 | history | edited | Reinstate Monica | CC BY-SA 3.0 |
updated to reflect that input length is log(n), not n
|
| Jun 21, 2016 at 21:40 | comment | added | Reinstate Monica | @mdfst13 You are right. I will update my answer. | |
| Apr 14, 2016 at 19:16 | vote | accept | would_like_to_be_anon | ||
| Mar 9, 2016 at 22:27 | comment | added | vnp |
Sorry, got carried away. Of course there is no logarithmic solution. What I had in mind is that popcount((x ^ (x - 1)) - 1 gives the length of a run of zeroes from least significant in a constant time. Then shift right by the run length, negate, get rid of run of (used to be) ones and negate again to reach next run of zeroes. Surely still linear.
|
|
| Mar 9, 2016 at 22:01 | comment | added | Reinstate Monica | @vnp Constant popcount sounds unrealistic because in some sense it has to scan the whole number (but note that I counted my shift and mask as constant, which is technically incorrect, but I am assuming there would be a way to select a bit in constant time). Regardless, how would this logarithmic algorithm work? | |
| Mar 9, 2016 at 21:51 | comment | added | vnp |
For an arbitrary large int, if we pretend that instructions - including popcount - execute in constant time, there is a logarithmic solution.
|
|
| Mar 9, 2016 at 20:39 | history | edited | Reinstate Monica | CC BY-SA 3.0 |
corrected bug
|
| Mar 9, 2016 at 20:18 | history | edited | Reinstate Monica | CC BY-SA 3.0 |
added 350 characters in body
|
| Mar 9, 2016 at 20:14 | comment | added | Andriy Kryvtsun | ...and complexity is \$O(n)\$ | |
| Mar 9, 2016 at 20:12 | history | answered | Reinstate Monica | CC BY-SA 3.0 |