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?

`(format "%08x" (-> 0xf2345678 (unsigned-bit-shift-right 4)))` gives you the answer you want by using longs the whole way through. Is there some reason you can't use longs for what you're doing, perhaps by only paying attention to the lower 32 bits? — gfredericks, Jan 21 '16 at 02:57
One possibility: explicitly mask your int before shifting, so that it doesn’t get turned into a negative 64 bit val: `(unsigned-bit-shift-right (bit-and (unchecked-int 0xf2345678) 0xffffffff) 4)`. (In fact you might not need `unchecked-int` here.) — matt, Jan 21 '16 at 03:24

score 5 · Accepted Answer · answered Jan 21 '16 at 04:02

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.

Clojure deftype:

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

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.

Clojure expression:

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

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

Looks good, but `#(unsigned-bit-shift-right-int % 32)` seems to be identity for some reason, when I would have expected it to be the constant 0 function. — Cactus, Jan 21 '16 at 12:45
The JVM's unsigned right shift instruction only uses the 5 lowest-order bits of the right operand. So, `x >>> 32` is equivalent to `x >>> 0` and `System.out.println(1 >>> 32)` prints `1` in Java. This is specified in *The Java® Language Specification: Java SE 8 Edition*, §15.19 Shift Operators, page 563. — Michał Marczyk, Jan 21 '16 at 12:57

Right-shifting 32-bit ints

1 Answers1

Inlined with primitive arguments:

Inlined with non-primitive arguments: