Swap bits with their neighbours
Python 2, 26 bytes
lambda n:2*n-3*(4**n/3&n/2)
Bit tricks!
Say n
has form ...ghfedcba
in binary. Then, we can split it into every other bit as
n = o + 2*e
n = ...hgfedcba
o = ...0g0e0c0a
2*e = ...h0f0d0b0
Then, the bit-switched result s
can be expressed as s=2*o+e
.
s = 2*o + e
s = ...ghefcdab
2*o = ...g0e0c0a0
e = ...0h0f0d0b
We'd rather compute only one of e
and o
, so we express o=n-2*e
and substitute
s=2*(n-2*e)+e = 2*n-3*e
So, now it remains to express e
in terms of n
. The number M=4**n/3
has form ...10101010101
in binary, which serves as a mask for the odd digits. The exponent n
ensures that M
is long enough. Taking the bitwise and
of n/2
and this value gives e
as desired.
n/2 = ...hgfedcb
M = ...1010101
n/2 & M = ...h0f0d0b = e
We can instead express e
in terms of o
e=(n-o)/2
, which gives s=(n+o*3)/2
, which saves a byte thanks to an optimization from xsot.
lambda n:n+(n&4**n/3)*3>>1
C function, 38
Bit-twiddling:
f(x){return(x&~0U/3*2)/2+(x&~0U/3)*2;}
Ideone.
Or for the fun of it:
C recursive function, 43
As per the OEIS formula, a(4n+k) = 4a(n) + a(k), 0 <= k <= 3
f(x){return x>3?4*f(x/4)+f(x%4):x%3?3-x:x;}
or
f(x){return x>3?4*f(x/4)+f(x%4):x%2*2+x/2;}
Ideone.
Jelly, 10 9 7 bytes
b4d2UFḄ
Try it online! or verify all test cases.
How it works
b4d2UFḄ Main link. Argument: n (integer)
b4 Convert n to base 4.
d2 Divmod each quaternary digit x by 2, yielding [x : 2, x % 2].
U Upend; reverse each pair, yielding [x % 2, x : 2].
F Flatten the 2D list of binary digits.
Ḅ Convert from binary to integer.