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.