From comments:
> But, this code never stops (because of integer overflow) !?! Yves Daoust
For many numbers it will *not* overflow.
If it *will* overflow - for one of those unlucky initial seeds, the overflown number will very likely converge toward 1 without another overflow.
Still this poses interesting question, is there some overflow-cyclic seed number?
Any simple final converging series starts with power of two value (obvious enough?).
2^64 will overflow to zero, which is undefined infinite loop according to algorithm (ends only with 1), but the most optimal solution in answer will finish due to `shr rax` producing ZF=1.
Can we produce 2^64? If the starting number is `0x5555555555555555`, it's odd number, next number is then 3n+1, which is `0xFFFFFFFFFFFFFFFF + 1` = `0`. Theoretically in undefined state of algorithm, but the optimized answer of johnfound will recover by exiting on ZF=1. The `cmp rax,1` of Peter Cordes **will end in infinite loop** (QED variant 1, "cheapo" through undefined `0` number).
How about some more complex number, which will create cycle without `0`?
Frankly, I'm not sure, my Math theory is too hazy to get any serious idea, how to deal with it in serious way. But intuitively I would say the series will converge to 1 for every number : 0 < number, as the 3n+1 formula will slowly turn every non-2 prime factor of original number (or intermediate) into some power of 2, sooner or later. So we don't need to worry about infinite loop for original series, only overflow can hamper us.
So I just put few numbers into sheet and took a look on 8 bit truncated numbers.
There are three values overflowing to `0`: `227`, `170` and `85` (`85` going directly to `0`, other two progressing toward `85`).
But there's no value creating cyclic overflow seed.
Funnily enough I did a check, which is the first number to suffer from 8 bit truncation, and already `27` is affected! It does reach value `9232` in proper non-truncated series (first truncated value is `322` in 12th step), and the maximum value reached for any of the 2-255 input numbers in non-truncated way is `13120` (for the `255` itself), maximum number of steps to converge to `1` is about `128` (+-2, not sure if "1" is to count, etc...).
Interestingly enough (for me) the number `9232` is maximum for many other source numbers, what's so special about it? :-O `9232` = `0x2410` ... hmmm.. no idea.
Unfortunately I can't get any deep grasp of this series, why does it converge and what are the implications of truncating them to *k* bits, but with `cmp number,1` terminating condition it's certainly possible to put the algorithm into infinite loop with particular input value ending as `0` after truncation.
But the value `27` overflowing for 8 bit case is sort of alerting, this looks like if you count the number of steps to reach value `1`, you will get wrong result for majority of numbers from the total k-bit set of integers. For the 8 bit integers the 146 numbers out of 256 have affected series by truncation (some of them may still hit the correct number of steps by accident maybe, I'm too lazy to check).