Checked in David's update to LongMap and IntMap.

2 files changed, 23 insertions, 2 deletions

diff --git a/src/library/scala/collection/immutable/IntMap.scala b/src/library/scala/collection/immutable/IntMap.scala
index 71b10610a3..0d54fcd671 100644
--- a/src/library/scala/collection/immutable/IntMap.scala
+++ b/src/library/scala/collection/immutable/IntMap.scala
@@ -7,7 +7,17 @@ private[immutable] object IntMapUtils{
   def unsignedCompare(i : Int, j : Int) = (i < j) ^ (i < 0) ^ (j < 0)
   def shorter(m1 : Int, m2 : Int) = unsignedCompare(m2, m1)
   def complement(i : Int) = (-1) ^ i;
-  def branchMask(i : Int, j : Int) = java.lang.Integer.highestOneBit(i ^ j);
+  def highestOneBit(j : Int) = {
+    var i = j;
+    i |= (i >>  1);
+    i |= (i >>  2);
+    i |= (i >>  4);
+    i |= (i >>  8);
+    i |= (i >> 16);
+    i - (i >>> 1);
+  }
+
+  def branchMask(i : Int, j : Int) = highestOneBit(i ^ j);
 
   def join[T](p1 : Int, t1 : IntMap[T], p2 : Int, t2 : IntMap[T]) : IntMap[T] = {
     val m = branchMask(p1, p2);
diff --git a/src/library/scala/collection/immutable/LongMap.scala b/src/library/scala/collection/immutable/LongMap.scala
index b23537aca6..953a89952e 100644
--- a/src/library/scala/collection/immutable/LongMap.scala
+++ b/src/library/scala/collection/immutable/LongMap.scala
@@ -7,7 +7,18 @@ private[immutable] object LongMapUtils{
   def unsignedCompare(i : Long, j : Long) = (i < j) ^ (i < 0) ^ (j < 0)
   def shorter(m1 : Long, m2 : Long) = unsignedCompare(m2, m1)
   def complement(i : Long) = (-1) ^ i;
-  def branchMask(i : Long, j : Long) = java.lang.Long.highestOneBit(i ^ j);
+  def branchMask(i : Long, j : Long) = highestOneBit(i ^ j);
+
+  def highestOneBit(j : Long) = {
+    var i = j;
+    i |= (i >>  1);
+    i |= (i >>  2);
+    i |= (i >>  4);
+    i |= (i >>  8);
+    i |= (i >> 16);
+    i |= (i >> 32);
+    i - (i >>> 1);
+  }
 
   def join[T](p1 : Long, t1 : LongMap[T], p2 : Long, t2 : LongMap[T]) : LongMap[T] = {
     val m = branchMask(p1, p2);