Packages
fixpoint
0.20.6
0.22.1
0.21.5
0.21.4
0.21.3
0.21.2
0.21.1
0.21.0
0.20.6
0.20.5
0.20.4
0.20.3
0.20.2
0.20.1
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.18.2
0.18.1
0.17.6
0.17.5
0.17.4
0.17.3
0.17.2
0.17.1
0.16.5
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.6
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.9
0.14.8
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.13.5
0.13.4
0.13.2
0.13.1
0.12.9
0.12.8
0.12.7
0.12.6
0.12.5
0.12.4
0.12.2
0.12.1
0.11.8
0.11.7
0.11.6
0.11.5
0.11.4
0.11.3
0.11.2
0.11.1
0.10.7
0.10.6
0.10.5
0.10.4
0.10.3
0.10.2
0.10.1
0.9.12
0.9.11
0.9.10
0.9.9
0.9.8
0.9.7
0.9.6
0.9.5
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.8.52
0.8.51
0.8.50
0.8.49
0.8.48
0.8.46
0.8.44
0.8.43
0.8.42
0.8.41
0.8.40
0.8.39
0.8.38
0.8.37
0.8.36
0.8.35
0.8.34
0.8.33
0.8.32
0.8.31
0.8.30
0.8.29
0.8.28
0.8.27
0.8.26
0.8.25
0.8.24
0.8.23
0.8.22
0.8.21
0.8.20
0.8.19
0.8.18
0.8.17
0.8.16
0.8.15
0.8.14
0.8.13
0.8.12
0.8.11
0.8.10
0.8.9
0.8.8
0.8.7
0.8.6
0.8.5
0.8.4
0.8.3
0.8.2
0.8.1
0.8.0
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.12
0.5.11
0.5.10
0.5.9
0.5.8
0.5.7
0.5.6
0.5.5
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.6
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.1.3
0.1.2
0.1.1
0.1.0
Constraint Programming Solver
Current section
Files
Jump to
Current section
Files
lib/utils/bit_utils.ex
defmodule CPSolver.BitUtils do
import Bitwise
@all_ones_mask (1 <<< 64) - 1
## Find least significant bit for given number
def lsb(n, method \\ :debruijn)
def lsb(0, _method) do
nil
end
def lsb(n, :shift) do
lsb_impl(n, 0)
end
def lsb(n, :debruijn) do
sequence = 0x022FDD63CC95386D
## Complement, multiply and normalize to 64-bit
normalized = (n &&& -n) * sequence &&& @all_ones_mask
## Use first 6 bits to locate in index table
## || lsb(n, :shift)
deBruijnTable(sequence, normalized >>> 58)
end
defp lsb_impl(1, idx) do
idx
end
defp lsb_impl(n, idx) do
((n &&& 1) == 1 && idx) ||
lsb_impl(n >>> 1, idx + 1)
end
## Find most significant bit for given number
def msb(n, method \\ :debruijn)
def msb(0, _method), do: nil
def msb(n, :debruijn) do
sequence = 0x03F79D71B4CB0A89
if n > 0 do
n = n ||| n >>> 1
n = n ||| n >>> 2
n = n ||| n >>> 4
n = n ||| n >>> 8
n = n ||| n >>> 16
n = n ||| n >>> 32
normalized = (n * sequence) &&& @all_ones_mask
deBruijnTable(sequence, normalized >>> 58)
end
end
def msb(n, :log2) do
if n > 0 do
n = n ||| n >>> 1
n = n ||| n >>> 2
n = n ||| n >>> 4
n = n ||| n >>> 8
n = n ||| n >>> 16
n = n ||| n >>> 32
log2(n - (n >>> 1))
end
end
def bit_count(0) do
0
end
def bit_count(n) do
n = (n &&& 0x5555555555555555) + (n >>> 1 &&& 0x5555555555555555)
n = (n &&& 0x3333333333333333) + (n >>> 2 &&& 0x3333333333333333)
n = (n &&& 0x0F0F0F0F0F0F0F0F) + (n >>> 4 &&& 0x0F0F0F0F0F0F0F0F)
n = (n &&& 0x00FF00FF00FF00FF) + (n >>> 8 &&& 0x00FF00FF00FF00FF)
n = (n &&& 0x0000FFFF0000FFFF) + (n >>> 16 &&& 0x0000FFFF0000FFFF)
(n &&& 0x00000000FFFFFFFF) + (n >>> 32 &&& 0x00000000FFFFFFFF)
end
## Precompiled log2 values for powers of 2
defp log2(1), do: 0
defp log2(2), do: 1
defp log2(4), do: 2
defp log2(8), do: 3
defp log2(16), do: 4
defp log2(32), do: 5
defp log2(64), do: 6
defp log2(128), do: 7
defp log2(256), do: 8
defp log2(512), do: 9
defp log2(1024), do: 10
defp log2(2048), do: 11
defp log2(4096), do: 12
defp log2(8192), do: 13
defp log2(16384), do: 14
defp log2(32768), do: 15
defp log2(65536), do: 16
defp log2(131_072), do: 17
defp log2(262_144), do: 18
defp log2(524_288), do: 19
defp log2(1_048_576), do: 20
defp log2(2_097_152), do: 21
defp log2(4_194_304), do: 22
defp log2(8_388_608), do: 23
defp log2(16_777_216), do: 24
defp log2(33_554_432), do: 25
defp log2(67_108_864), do: 26
defp log2(134_217_728), do: 27
defp log2(268_435_456), do: 28
defp log2(536_870_912), do: 29
defp log2(1_073_741_824), do: 30
defp log2(2_147_483_648), do: 31
defp log2(4_294_967_296), do: 32
defp log2(8_589_934_592), do: 33
defp log2(17_179_869_184), do: 34
defp log2(34_359_738_368), do: 35
defp log2(68_719_476_736), do: 36
defp log2(137_438_953_472), do: 37
defp log2(274_877_906_944), do: 38
defp log2(549_755_813_888), do: 39
defp log2(1_099_511_627_776), do: 40
defp log2(2_199_023_255_552), do: 41
defp log2(4_398_046_511_104), do: 42
defp log2(8_796_093_022_208), do: 43
defp log2(17_592_186_044_416), do: 44
defp log2(35_184_372_088_832), do: 45
defp log2(70_368_744_177_664), do: 46
defp log2(140_737_488_355_328), do: 47
defp log2(281_474_976_710_656), do: 48
defp log2(562_949_953_421_312), do: 49
defp log2(1_125_899_906_842_624), do: 50
defp log2(2_251_799_813_685_248), do: 51
defp log2(4_503_599_627_370_496), do: 52
defp log2(9_007_199_254_740_992), do: 53
defp log2(18_014_398_509_481_984), do: 54
defp log2(36_028_797_018_963_968), do: 55
defp log2(72_057_594_037_927_936), do: 56
defp log2(144_115_188_075_855_872), do: 57
defp log2(288_230_376_151_711_744), do: 58
defp log2(576_460_752_303_423_488), do: 59
defp log2(1_152_921_504_606_846_976), do: 60
defp log2(2_305_843_009_213_693_952), do: 61
defp log2(4_611_686_018_427_387_904), do: 62
defp log2(9_223_372_036_854_775_808), do: 63
## De Bruijn table for sequence 0x022FDD63CC95386D
## Used for LSB
defp deBruijnTable(0x022FDD63CC95386D, 0), do: 0
defp deBruijnTable(0x022FDD63CC95386D, 1), do: 1
defp deBruijnTable(0x022FDD63CC95386D, 2), do: 2
defp deBruijnTable(0x022FDD63CC95386D, 3), do: 53
defp deBruijnTable(0x022FDD63CC95386D, 4), do: 3
defp deBruijnTable(0x022FDD63CC95386D, 5), do: 7
defp deBruijnTable(0x022FDD63CC95386D, 6), do: 54
defp deBruijnTable(0x022FDD63CC95386D, 7), do: 27
defp deBruijnTable(0x022FDD63CC95386D, 8), do: 4
defp deBruijnTable(0x022FDD63CC95386D, 9), do: 38
defp deBruijnTable(0x022FDD63CC95386D, 10), do: 41
defp deBruijnTable(0x022FDD63CC95386D, 11), do: 8
defp deBruijnTable(0x022FDD63CC95386D, 12), do: 34
defp deBruijnTable(0x022FDD63CC95386D, 13), do: 55
defp deBruijnTable(0x022FDD63CC95386D, 14), do: 48
defp deBruijnTable(0x022FDD63CC95386D, 15), do: 28
defp deBruijnTable(0x022FDD63CC95386D, 16), do: 62
defp deBruijnTable(0x022FDD63CC95386D, 17), do: 5
defp deBruijnTable(0x022FDD63CC95386D, 18), do: 39
defp deBruijnTable(0x022FDD63CC95386D, 19), do: 46
defp deBruijnTable(0x022FDD63CC95386D, 20), do: 44
defp deBruijnTable(0x022FDD63CC95386D, 21), do: 42
defp deBruijnTable(0x022FDD63CC95386D, 22), do: 22
defp deBruijnTable(0x022FDD63CC95386D, 23), do: 9
defp deBruijnTable(0x022FDD63CC95386D, 24), do: 24
defp deBruijnTable(0x022FDD63CC95386D, 25), do: 35
defp deBruijnTable(0x022FDD63CC95386D, 26), do: 59
defp deBruijnTable(0x022FDD63CC95386D, 27), do: 56
defp deBruijnTable(0x022FDD63CC95386D, 28), do: 49
defp deBruijnTable(0x022FDD63CC95386D, 29), do: 18
defp deBruijnTable(0x022FDD63CC95386D, 30), do: 29
defp deBruijnTable(0x022FDD63CC95386D, 31), do: 11
defp deBruijnTable(0x022FDD63CC95386D, 32), do: 63
defp deBruijnTable(0x022FDD63CC95386D, 33), do: 52
defp deBruijnTable(0x022FDD63CC95386D, 34), do: 6
defp deBruijnTable(0x022FDD63CC95386D, 35), do: 26
defp deBruijnTable(0x022FDD63CC95386D, 36), do: 37
defp deBruijnTable(0x022FDD63CC95386D, 37), do: 40
defp deBruijnTable(0x022FDD63CC95386D, 38), do: 33
defp deBruijnTable(0x022FDD63CC95386D, 39), do: 47
defp deBruijnTable(0x022FDD63CC95386D, 40), do: 61
defp deBruijnTable(0x022FDD63CC95386D, 41), do: 45
defp deBruijnTable(0x022FDD63CC95386D, 42), do: 43
defp deBruijnTable(0x022FDD63CC95386D, 43), do: 21
defp deBruijnTable(0x022FDD63CC95386D, 44), do: 23
defp deBruijnTable(0x022FDD63CC95386D, 45), do: 58
defp deBruijnTable(0x022FDD63CC95386D, 46), do: 17
defp deBruijnTable(0x022FDD63CC95386D, 47), do: 10
defp deBruijnTable(0x022FDD63CC95386D, 48), do: 51
defp deBruijnTable(0x022FDD63CC95386D, 49), do: 25
defp deBruijnTable(0x022FDD63CC95386D, 50), do: 36
defp deBruijnTable(0x022FDD63CC95386D, 51), do: 32
defp deBruijnTable(0x022FDD63CC95386D, 52), do: 60
defp deBruijnTable(0x022FDD63CC95386D, 53), do: 20
defp deBruijnTable(0x022FDD63CC95386D, 54), do: 57
defp deBruijnTable(0x022FDD63CC95386D, 55), do: 16
defp deBruijnTable(0x022FDD63CC95386D, 56), do: 50
defp deBruijnTable(0x022FDD63CC95386D, 57), do: 31
defp deBruijnTable(0x022FDD63CC95386D, 58), do: 19
defp deBruijnTable(0x022FDD63CC95386D, 59), do: 15
defp deBruijnTable(0x022FDD63CC95386D, 60), do: 30
defp deBruijnTable(0x022FDD63CC95386D, 61), do: 14
defp deBruijnTable(0x022FDD63CC95386D, 62), do: 13
defp deBruijnTable(0x022FDD63CC95386D, 63), do: 12
## De Bruijn table for sequence 0x03F79D71B4CB0A89
## Used for MSB
defp deBruijnTable(0x03F79D71B4CB0A89, 0), do: 0
defp deBruijnTable(0x03F79D71B4CB0A89, 1), do: 47
defp deBruijnTable(0x03F79D71B4CB0A89, 2), do: 1
defp deBruijnTable(0x03F79D71B4CB0A89, 3), do: 56
defp deBruijnTable(0x03F79D71B4CB0A89, 4), do: 48
defp deBruijnTable(0x03F79D71B4CB0A89, 5), do: 27
defp deBruijnTable(0x03F79D71B4CB0A89, 6), do: 2
defp deBruijnTable(0x03F79D71B4CB0A89, 7), do: 60
defp deBruijnTable(0x03F79D71B4CB0A89, 8), do: 57
defp deBruijnTable(0x03F79D71B4CB0A89, 9), do: 49
defp deBruijnTable(0x03F79D71B4CB0A89, 10), do: 41
defp deBruijnTable(0x03F79D71B4CB0A89, 11), do: 37
defp deBruijnTable(0x03F79D71B4CB0A89, 12), do: 28
defp deBruijnTable(0x03F79D71B4CB0A89, 13), do: 16
defp deBruijnTable(0x03F79D71B4CB0A89, 14), do: 3
defp deBruijnTable(0x03F79D71B4CB0A89, 15), do: 61
defp deBruijnTable(0x03F79D71B4CB0A89, 16), do: 54
defp deBruijnTable(0x03F79D71B4CB0A89, 17), do: 58
defp deBruijnTable(0x03F79D71B4CB0A89, 18), do: 35
defp deBruijnTable(0x03F79D71B4CB0A89, 19), do: 52
defp deBruijnTable(0x03F79D71B4CB0A89, 20), do: 50
defp deBruijnTable(0x03F79D71B4CB0A89, 21), do: 42
defp deBruijnTable(0x03F79D71B4CB0A89, 22), do: 21
defp deBruijnTable(0x03F79D71B4CB0A89, 23), do: 44
defp deBruijnTable(0x03F79D71B4CB0A89, 24), do: 38
defp deBruijnTable(0x03F79D71B4CB0A89, 25), do: 32
defp deBruijnTable(0x03F79D71B4CB0A89, 26), do: 29
defp deBruijnTable(0x03F79D71B4CB0A89, 27), do: 23
defp deBruijnTable(0x03F79D71B4CB0A89, 28), do: 17
defp deBruijnTable(0x03F79D71B4CB0A89, 29), do: 11
defp deBruijnTable(0x03F79D71B4CB0A89, 30), do: 4
defp deBruijnTable(0x03F79D71B4CB0A89, 31), do: 62
defp deBruijnTable(0x03F79D71B4CB0A89, 32), do: 46
defp deBruijnTable(0x03F79D71B4CB0A89, 33), do: 55
defp deBruijnTable(0x03F79D71B4CB0A89, 34), do: 26
defp deBruijnTable(0x03F79D71B4CB0A89, 35), do: 59
defp deBruijnTable(0x03F79D71B4CB0A89, 36), do: 40
defp deBruijnTable(0x03F79D71B4CB0A89, 37), do: 36
defp deBruijnTable(0x03F79D71B4CB0A89, 38), do: 15
defp deBruijnTable(0x03F79D71B4CB0A89, 39), do: 53
defp deBruijnTable(0x03F79D71B4CB0A89, 40), do: 34
defp deBruijnTable(0x03F79D71B4CB0A89, 41), do: 51
defp deBruijnTable(0x03F79D71B4CB0A89, 42), do: 20
defp deBruijnTable(0x03F79D71B4CB0A89, 43), do: 43
defp deBruijnTable(0x03F79D71B4CB0A89, 44), do: 31
defp deBruijnTable(0x03F79D71B4CB0A89, 45), do: 22
defp deBruijnTable(0x03F79D71B4CB0A89, 46), do: 10
defp deBruijnTable(0x03F79D71B4CB0A89, 47), do: 45
defp deBruijnTable(0x03F79D71B4CB0A89, 48), do: 25
defp deBruijnTable(0x03F79D71B4CB0A89, 49), do: 39
defp deBruijnTable(0x03F79D71B4CB0A89, 50), do: 14
defp deBruijnTable(0x03F79D71B4CB0A89, 51), do: 33
defp deBruijnTable(0x03F79D71B4CB0A89, 52), do: 19
defp deBruijnTable(0x03F79D71B4CB0A89, 53), do: 30
defp deBruijnTable(0x03F79D71B4CB0A89, 54), do: 9
defp deBruijnTable(0x03F79D71B4CB0A89, 55), do: 24
defp deBruijnTable(0x03F79D71B4CB0A89, 56), do: 13
defp deBruijnTable(0x03F79D71B4CB0A89, 57), do: 18
defp deBruijnTable(0x03F79D71B4CB0A89, 58), do: 8
defp deBruijnTable(0x03F79D71B4CB0A89, 59), do: 12
defp deBruijnTable(0x03F79D71B4CB0A89, 60), do: 7
defp deBruijnTable(0x03F79D71B4CB0A89, 61), do: 6
defp deBruijnTable(0x03F79D71B4CB0A89, 62), do: 5
defp deBruijnTable(0x03F79D71B4CB0A89, 63), do: 63
end