Right-shifting 32-bit ints

Question

Clojure's bit-shift operations all seem to return 64-bit long results, even for 32-bit int arguments. This is not a substantial problem for bit-shift-left:

user=> (format "%08x" (unchecked-int (bit-shift-left (unchecked-int 0x12345678) 4)))
"23456780"
user=> (format "%08x" (unchecked-int (bit-shift-left (unchecked-int 0xf2345678) 4)))
"23456780"

However, this becomes a problem for unsigned right-shifting of negative numbers:

user=> (format "%08x" (unchecked-int (unsigned-bit-shift-right (unchecked-int 0xf2345678) 4)))
"ff234567"

The correct answer, of course, would be 0f234567.

What is the most efficient way to implement 32-bit unsigned right-shifting in Clojure?

Answer 1

This can be accomplished by calling the int clojure.lang.Numbers.unsignedShiftRightInt(int, int) method which uses >>> on int arguments, returning int. It's not currently exposed as a function anywhere, but it does have an intrinsic implementation (equivalent to >>> in Java) and you can either call it directly or wrap in your own inlinable function:

(defn unsigned-bit-shift-right-int
  {:inline (fn [x n] `(clojure.lang.Numbers/unsignedShiftRightInt ~x ~n))}
  [x n]
  (clojure.lang.Numbers/unsignedShiftRightInt x n))

This returns the correct value whether it gets inlined or not, but of course generally you'd want it to be inlined. It's also good to make sure that the arguments are actually primitive ints so that the intrinsic can kick in.

Here's what it compiles to in Clojure 1.8 in the two possible cases where it does get inlined (the non-inlined case is a regular function call, nothing to see there):

Inlined with primitive arguments:

Abusing count a little bit just to illustrate the point. Note the iushr instruction.

1. Clojure deftype:

   (deftype Foo [^int x ^int y]
     clojure.lang.Counted
     (count [this]
       (unsigned-bit-shift-right-int x y)))
   

2. Bytecode:

   // Method descriptor #61 ()I
   // Stack: 2, Locals: 1
   public int count();
      0  aload_0 [this]
      1  getfield user.Foo.x : int [19]
      4  aload_0 [this]
      5  getfield user.Foo.y : int [21]
      8  iushr
      9  ireturn
       Line numbers:
         [pc: 0, line: 1]
         [pc: 8, line: 4]
       Local variable table:
         [pc: 0, pc: 9] local: this index: 0 type: user.Foo
   

Inlined with non-primitive arguments:

Note the invokestatic clojure.lang.Numbers.unsignedShiftRight… instruction.

1. Clojure expression:

   #(format "%08x"
      (clojure.lang.Numbers/unsignedShiftRightInt (unchecked-int 0xf2345678) 4))
   

2. Bytecode:

   // Method descriptor #11 ()Ljava/lang/Object;
   // Stack: 5, Locals: 1
   public java.lang.Object invoke();
      0  getstatic user$eval16141$fn__16142.const__0 : clojure.lang.Var [15]
      3  invokevirtual clojure.lang.Var.getRawRoot() : java.lang.Object [20]
      6  checkcast clojure.lang.IFn [22]
      9  ldc <String "%08x"> [24]
     11  ldc2_w <Long 4063516280> [25]
     14  l2i
     15  ldc2_w <Long 4> [27]
     18  invokestatic clojure.lang.RT.intCast(long) : int [34]
     21  invokestatic clojure.lang.Numbers.unsignedShiftRightInt(int, int) : int [40]
     24  invokestatic java.lang.Integer.valueOf(int) : java.lang.Integer [46]
     27  invokeinterface clojure.lang.IFn.invoke(java.lang.Object, java.lang.Object) : java.lang.Object [49] [nargs: 3]
     32  areturn
       Line numbers:
         [pc: 0, line: 1]
         [pc: 6, line: 1]
         [pc: 14, line: 1]
         [pc: 21, line: 1]
         [pc: 27, line: 1]
       Local variable table:
         [pc: 0, pc: 32] local: this index: 0 type: java.lang.Object