sourcelibs/Bits/src/Bits.xtl
1⍝# Bits: bits -- binary digits and back, popcount, and, or, xor on
2⍝# whole numbers, shifts, single bits, Gray codes.
3⍝# Import it with an alias of your choice: "b:" u_se< "Bits".
4⍝# Put libs/Bits/src on XETAL_PATH ("just path"); the reference is libs/Bits/docs.
5⍝# Names with l: are exported; those under h: are private to this file.
6⍝#
7⍝# Numbers are whole and at least 0 (up to 2^62); bit 0 is the lowest.
8⍝# The logic works on every item at once: the numbers are taken apart
9⍝# into bits with e_ncode, combined with the built-in &, | and !=, and
10⍝# put back together with d_ecode. On vectors of bits those built-ins
11⍝# are the logic already.
12
13w ← 63 ⍝ bits taken from each number
14
15⍝## Columns and value
16
17⍝# The w bits of each number, one column per number.
18ʰc̲ols ← { x →
19 '∨ r̲/ r̲avel x < 0 ? @ p̲anic< "Bits works on whole numbers 0 or more, not {x}"
20 (w r̲eshape 2) e̲ncode x
21}
22
23⍝# n b_its x: the low n bits of each number, most significant first: a
24⍝# vector for one number, a row per number for several.
25ˡb̲its ← { n x →
26 '∨ r̲/ r̲avel x < 0 ? @ p̲anic< "Bits works on whole numbers 0 or more, not {x}"
27 o̲\ (n r̲eshape 2) e̲ncode x
28}
29
30⍝# v_alue bits: the number each row of bits (or the vector) stands for.
31ˡv̲alue ← { bits → 2 d̲ecode o̲\ bits }
32
33⍝## Bit by bit
34
35⍝# p_opcount x: how many 1 bits each number has.
36ˡp̲opcount ← { x → '+ r̲/ ʰc̲ols x }
37
38⍝# a a_nd b, a o_r b, a x_or b: bit by bit, item by item (a single
39⍝# number on either side goes with every item of the other: a + 0 * b
40⍝# has the shape of both). On 0/1 digits: and is the smaller, or the
41⍝# larger, xor the distance; Int arithmetic keeps the result an Int (a
42⍝# comparison such as & would leave its numeric type to the caller: ask
43⍝# X17).
44ˡa̲nd ← { a b → 2 d̲ecode (ʰc̲ols a + 0 × b) m̲in ʰc̲ols b + 0 × a }
45ˡo̲r ← { a b → 2 d̲ecode (ʰc̲ols a + 0 × b) m̲ax ʰc̲ols b + 0 × a }
46ˡx̲or ← { a b → 2 d̲ecode a̲bs (ʰc̲ols a + 0 × b) − ʰc̲ols b + 0 × a }
47
48⍝## Shifts and masks
49
50⍝# n s_hl x, n s_hr x: each number shifted n bits left (times 2^n) or
51⍝# right (halved n times, dropping the bits shifted out).
52ˡs̲hl ← { n x → x × 2 ^ n }
53ˡs̲hr ← { n x → x d̲iv 2 ^ n }
54
55⍝# i b_it? x: whether bit i of each number is 1.
56ˡb̲it? ← { i x → 1 = (x d̲iv 2 ^ i) m̲od 2 }
57
58⍝# m_ask n: the number whose low n bits are 1.
59ˡm̲ask ← { n → (2 ^ n) − 1 }
60
61⍝## Gray code
62
63⍝# g_ray x: the Gray code of each number (neighbors differ in one bit);
64⍝# u_ngray g: back again.
65ˡg̲ray ← { x → x ˡx̲or 1 ˡs̲hr x }
66ˡu̲ngray ← { g → 2 d̲ecode '≠ s̲\ ʰc̲ols g }