{"issue":{"state":"open","created_at":"2011-12-04T07:57:48Z","updated_at":"2011-12-04T07:57:49Z","comments":0,"user":{"gravatar_id":"9f097a7a9885f3cc2ab43273ae1d2193","id":177228,"url":"https://api.github.com/users/nolanw","login":"nolanw","avatar_url":"https://secure.gravatar.com/avatar/9f097a7a9885f3cc2ab43273ae1d2193?d=https://a248.e.akamai.net/assets.github.com%2Fimages%2Fgravatars%2Fgravatar-140.png"},"body":"I'm curious about the proof you give, in section 12, for the statement \"the only non-zero values for which the sets of true bits for `x` and `x − 1` are disjoint, are powers of two\". It seems incomplete to me.\r\n\r\nYou divide the number's bits up WLOG into three pieces: a (possibly empty) series of zeros, followed by a one, followed by a series ones and zeros. The number 1 (i.e. `0x01`) cannot be split as such.\r\n\r\n1 is of course a power of two, and the most-significant 1 is maintained as a result of the described operations, so I think all you need to do is point out that the third series of bits may also be empty.\r\n\r\n(P.S. Thanks for the awesome explanation, I was kind of lost with djb's relatively terse description.)","assignee":null,"id":2441058,"labels":[],"number":1,"pull_request":{"patch_url":null,"html_url":null,"diff_url":null},"title":"Incomplete proof that \"the only non-zero values for which the sets of true bits for x and x − 1 are disjoint, are powers of two\"","closed_at":null,"html_url":"https://github.com/agl/critbit/issues/1","url":"https://api.github.com/repos/agl/critbit/issues/1","milestone":null},"action":"opened"}