Packages
inplace
0.7.12
0.7.12
0.7.11
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.8
0.6.7
0.6.6
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.4
0.4.3
0.4.2
0.4.1
0.4.0
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.2.0
0.1.9
0.1.8
0.1.7
0.1.6
0.1.5
0.1.4
0.1.3
0.1.2
0.1.1
0.1.0
Mutable data structures
Current section
Files
Jump to
Current section
Files
lib/utils/bit_utils.ex
defmodule InPlace.BitUtils do
import Bitwise
@all_ones_mask (1 <<< 64) - 1
defguard is_64_bit(value) when value <= @all_ones_mask
## Check if the bit at (0-based) position is set
def bit_set?(n, position) when is_64_bit(n) do
(n &&& 1 <<< position) != 0
end
## Set/unset the bit at (0-based) position
##
def set_bit(n, position) when is_64_bit(n) do
n ||| (1 <<< position)
end
def unset_bit(n, position) when is_64_bit(n) do
n &&& (Bitwise.bnot(1 <<< position))
end
## Unfold into list
def to_list(0) do
[]
end
def to_list(n) when is_64_bit(n) do
Enum.reduce(lsb(n)..msb(n), [], fn p, acc -> (bit_set?(n, p) && [p | acc]) || acc end)
|> Enum.reverse()
end
## Find least significant bit for given number
def lsb(n, method \\ :debruijn)
def lsb(0, _method) do
nil
end
def lsb(n, :shift) when is_64_bit(n) do
lsb_impl(n, 0)
end
def lsb(n, :debruijn) when is_64_bit(n) 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) when is_64_bit(n) 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) when is_64_bit(n) 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) when is_64_bit(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