binary - No builtin function for bitwise rotation?

There appears to be no builtin Mathematica function for bitwise rotation. Is that true?

I suppose I can write my function:

ROR[x_, k_] := FromDigits[RotateRight[IntegerDigits[x, 2, 32], k]]

Obviously this will be a lot more inefficient than a builtin function because in machine code a rotate right is a single instruction. Is this my only option?

Answer

This should be reasonably efficient.

BitRotateRight[n_Integer, m_Integer] /; n > 0 && m >= 0 :=
  BitShiftRight[n, m] + BitShiftLeft[Mod[n, 2^m], (BitLength[n] - m)]

Will need to modify for left rotations if you want to support negative m. I added the restriction that n be positive. Not exactly sure what should be the behavior for negative n.

Quick example:

BitRotateRight[111, 5]

(* Out[2]= 63 *)


IntegerDigits[111, 2]

(* Out[3]= {1, 1, 0, 1, 1, 1, 1} *)

--- Edit ---

The question has been raised as to whether this approach is correct, or efficient for machine integers. Having looked more closely at the original post I agree it is not quite correct. The thing to do is to use a fixed length of e.g. 32 bits. I will show variants on this theme below. I hard-coded that lenght of 32 in several places. Obviously it could instead be an input parameter.

This is my first try, suitably modified, and made Listable for efficiency testing.

SetAttributes[BitRotateRight, Listable];

BitRotateRight[n_Integer, m_Integer] /; n > 0 && m >= 0 := 

 BitShiftRight[n, m] + BitShiftLeft[Mod[n, 2^m], (32 - m)]

Here is a compiled version.

BitRotateRightC = 
  Compile[{{n, _Integer}, {m, _Integer}}, 
   BitShiftRight[n, m] + BitShiftLeft[Mod[n, 2^m], (32 - m)], 
   RuntimeAttributes -> Listable];

Here is a variant that is not Listable but instead operates directly on a rank 1 tensor.

BitRotateRightC2 = 

  Compile[{{n, _Integer, 1}, {m, _Integer}}, 
   BitShiftRight[n, m] + BitShiftLeft[Mod[n, 2^m], (32 - m)]];

Last we'll show the code from the original post. I alter so that it computes, rather than shows, the machine integer result. Specifically, we use FromDigits to base 2 and do not try to show it as a bit string.

SetAttributes[ROR, Listable]
ROR[x_, k_] := FromDigits[RotateRight[IntegerDigits[x, 2, 32], k], 2]

We'll show testing on a list of a million or so machine integers.

n = 2^20;
SeedRandom[1111];

tt = RandomInteger[{0, 2^30}, n];

Timing[uu1 = BitRotateRight[tt, 3];]
(* Out[130]= {4.912000, Null} *)

Timing[uu2 = BitRotateRightC[tt, 3];]
(* Out[146]= {0.808000, Null} *)

Timing[uu2b = BitRotateRightC2[tt, 3];]
(* Out[147]= {0.044000, Null} *)


Timing[uu3 = ROR[tt, 3];]
(* Out[148]= {7.336000, Null} *)

I also did a version of ROR using Compile. It took about the same time as BitRotateRight. Also if I remove the positivity checks from BitRotateRight then it becomes somewhat faster (takes 3.2 seconds). So ROR is clearly slower, but not by all that much, than my first attempt.

Let's check for agreement.

uu1 = uu2 == uu2b == uu3
(* Out[149]= True *)

The middle two are of course packed array results. The outer ones are not. Compiling gives a factor of 5 improvement in speed, and working directly on a rank 1 tensor is an order of magnitude faster still.

--- End edit ---

--- Edit 2 ---

Actually it is best just to use basic listability, provided one is willing to forego type checking or do it differently than I had done. Suppose we clear prior definitions and then start with the one below.

BitRotateRight[n_, m_Integer] := 
 BitShiftRight[n, m] + BitShiftLeft[Mod[n, 2^m], (32 - m)]

Here is that example with 2^20 elements.

Timing[uu1b = BitRotateRight[tt, 3];]
(* Out[192]= {0.048000, Null} *)


In[193]:= uu1b == uu2
(* True *)

Probably I should just have done it this way from the beginning. That said, using Compile and showing runs that give no error or warning messages had its own advantage. It aptly demonstrates that the standard Mathematica evaluator is not being used. That is to say, the computation stays in the VM and runtime library. It was this secondary goal that (mis?)lead me in the compilation direction.

--- End edit 2 ---