login
Bit reversed 16-bit numbers.
2

%I #13 Jan 23 2018 06:43:17

%S 0,32768,16384,49152,8192,40960,24576,57344,4096,36864,20480,53248,

%T 12288,45056,28672,61440,2048,34816,18432,51200,10240,43008,26624,

%U 59392,6144,38912,22528,55296,14336,47104,30720,63488,1024,33792,17408,50176,9216,41984

%N Bit reversed 16-bit numbers.

%C The 16-bit analog of the 8-bit version A160638, see there for further links and information.

%C An involutive (i.e., equal to its own inverse) permutation of the numbers 0,...,65535.

%H Vincenzo Librandi, <a href="/A217589/b217589.txt">Table of n, a(n) for n = 0..10000</a>

%F a(a(n))=n.

%F a(m)+a(n)=a(m+n) whenever n & m = 0, where "&" is binary bit-AND, i.e., whenever m and n have no (1-)bits in common.

%F a(n) is even for all n < 2^15 = a(1) and odd for all larger n.

%F a(n) = floor(A030101(n+65536)/2). - _Reinhard Zumkeller_, Jan 12 2013

%t Table[FromDigits[Reverse[IntegerDigits[n, 2, 16]], 2], {n, 0, 50}] (* _T. D. Noe_, Oct 09 2012 *)

%o (PARI) a(n)=sum(i=0,15,bittest(n,15-i)<<i)

%o (Haskell)

%o import Data.Bits (testBit, setBit)

%o import Data.Word (Word16)

%o a217589 :: Word16 -> Word16

%o a217589 n = rev 0 0 where

%o rev 16 y = y

%o rev i y = rev (i + 1) (if testBit n i then setBit y (15 - i) else y)

%o -- _Reinhard Zumkeller_, Jan 12 2013

%K nonn,base,fini

%O 0,2

%A _M. F. Hasler_, Oct 07 2012