OFFSET
0,2
COMMENTS
This sequence is found in computer programs that need to reverse the bits in a byte, typically during data compression or other bit-level encoding. a(n) is its own inverse: a(a(n)) = n.
A permutation of the integers 0-255. - Jon Perry, Oct 06 2012
a(n) is even for 0 <= n< 128 and odd for n <= 128 < 256. - Jon Perry, Oct 06 2012
a(m) + a(n) = a(m+n) when the binary representations of m and n have no bits in common. - Jon Perry, Oct 06 2012
REFERENCES
Henry S. Warren, Hacker's Delight, Addison-Wesley, 2002, pages 101-106.
LINKS
Russ Cox, Table of n, a(n) for n = 0 .. 255 (full sequence)
Sean Anderson, Bit Twiddling Hacks
Michael Beeler, R. William Gosper and Richard C. Schroeppel, HAKMEM (MIT AI Memo 239, Feb. 29, 1972), Item 167.
FORMULA
a(n) = floor(A030101(n+256)/2). - Reinhard Zumkeller, Jan 12 2013
EXAMPLE
n = 1 = 00000001 binary, so a(1) = 10000000 binary = 128.
n = 29 = 00011101 binary, so a(29) = 10111000 binary = 184.
MATHEMATICA
a[n_] := FromDigits[PadLeft[IntegerDigits[n, 2], 8] // Reverse, 2]; Table[a[n], {n, 0, 255}] (* Jean-François Alcover, Dec 26 2015 *)
PROG
(C) int a = 0; for(int i=0; i<8; i++) if(n & (1<<i)) a |= 1<<(7 - i);
(PARI) A160638(n)=binary(n+256)*vector(9, n, 2^n)~\4 \\ M. F. Hasler, Oct 07 2012
(PARI) A160638(n)=sum(i=0, 7, bittest(n, 7-i)<<i) \\ M. F. Hasler, Oct 07 2012
(Haskell)
import Data.Bits (testBit, setBit)
import Data.Word (Word8)
a160638 :: Word8 -> Word8
a160638 n = rev 0 0 where
rev 8 y = y
rev i y = rev (i + 1) (if testBit n i then setBit y (7 - i) else y)
-- Reinhard Zumkeller, Jan 12 2013
(Python)
def a(n): return int(bin(n)[2:].zfill(8)[::-1], 2)
print([a(n) for n in range(256)]) # Michael S. Branicky, Jul 13 2022
CROSSREFS
KEYWORD
base,easy,fini,full,nonn,nice
AUTHOR
Russ Cox, May 21 2009
STATUS
approved