* Bill Gosper <billgosper@gmail.com> [Apr 04. 2014 18:40]:
Does this, in any sense, beat Knuth's? --rwg
Performance wise it should be identical (unless "rotate by one bit" is faster than "rotate by k bits" where k is an immediate operand); so WDS's benchmark looks dubious to me. But it has a (beholder and all that) lovelier end: all low 63 bits reversed, you can choose to leave the high bit alone or zero it out (by adding a one at the most significant bit of the first mask). Note that in terms of performance, the sequence to reverse bits in each byte (3 steps), followed by asm bswap (see fxtbook) will beat all we have here hands down. I'll give an idea to reverse 3^k bits in k steps (that is neat to know but fails for practical reasons) in the next days. Try to find it, it's next to trivial! Hint: what would you do if the words had 3^k bits? Best, jj
* Joerg Arndt <arndt@jjj.de> [Apr 03. 2014 17:09]:
ulong jj3_revbin(ulong x) { ulong z; z = (x ^ (x >> 2)) & 0x9249249249249249UL; x ^= z ^ (z << 2); // low 3 bits reversed z = (x ^ (x >> 6)) & 0x01c0e070381c0e07UL; x ^= z ^ (z << 6); // low 9 bits reversed z = (x ^ (x >> 18)) & 0x00001ff0000001ffUL; x ^= z ^ (z << 18); // low 27 bits reversed z = (x ^ (x >> 36)) & 0x0000000007ffffffUL; x ^= z ^ (z << 36); // low 63 bits reversed x = (x>>63) | (x<<1); // rotate left by 1 return x; }
Can explain if anybody is interested later, got a visitor now. Did run automated testing, but would appreciate independent "OK"s. Yes, tricky.
Best, jj
Brrrr, version above reverses 63 bits and clears the highest, next reverses all 64 bits, highest bit in first mask dropped now:
ulong jj3_revbin(ulong x) { ulong z; z = (x ^ (x >> 2)) & 0x1249249249249249UL; x ^= z ^ (z << 2); // ... rest as before ... } _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun