1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2013, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
package scala
package collection
package generic
/** Some bit operations.
*
* See http://www.drmaciver.com/2008/08/unsigned-comparison-in-javascala/ for
* an explanation of unsignedCompare.
*/
private[collection] object BitOperations {
trait Int {
type Int = scala.Int
def zero(i: Int, mask: Int) = (i & mask) == 0
def mask(i: Int, mask: Int) = i & (complement(mask - 1) ^ mask)
def hasMatch(key: Int, prefix: Int, m: Int) = mask(key, m) == prefix
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 bits(num: Int) = 31 to 0 by -1 map (i => (num >>> i & 1) != 0)
def bitString(num: Int, sep: String = "") = bits(num) map (b => if (b) "1" else "0") mkString sep
def highestOneBit(j: Int) = java.lang.Integer.highestOneBit(j)
}
object Int extends Int
trait Long {
type Long = scala.Long
def zero(i: Long, mask: Long) = (i & mask) == 0L
def mask(i: Long, mask: Long) = i & (complement(mask - 1) ^ mask)
def hasMatch(key: Long, prefix: Long, m: Long) = mask(key, m) == prefix
def unsignedCompare(i: Long, j: Long) = (i < j) ^ (i < 0L) ^ (j < 0L)
def shorter(m1: Long, m2: Long) = unsignedCompare(m2, m1)
def complement(i: Long) = (-1L) ^ i
def bits(num: Long) = 63L to 0L by -1L map (i => (num >>> i & 1L) != 0L)
def bitString(num: Long, sep: String = "") = bits(num) map (b => if (b) "1" else "0") mkString sep
def highestOneBit(j: Long) = java.lang.Long.highestOneBit(j)
}
object Long extends Long
}
|
