librarylibs/Bits/src/Bits.xtl

Bits: bits -- binary digits and back, popcount, and, or, xor on whole numbers, shifts, single bits, Gray codes. Import it with an alias of your choice: "b:" u_se< "Bits". Put libs/Bits/src on XETAL_PATH ("just path"); the reference is libs/Bits/docs. Names with l: are exported; those under h: are private to this file.

Numbers are whole and at least 0 (up to 2^62); bit 0 is the lowest. The logic works on every item at once: the numbers are taken apart into bits with e_ncode, combined with the built-in &, | and !=, and put back together with d_ecode. On vectors of bits those built-ins are the logic already.

source

w : Int

value (private) · line 13

w ← 63                                        ⍝ bits taken from each number

Used in: ʰc̲ols

Columns and value

ʰc̲ols : Int -> Int

function (private) · line 18

The w bits of each number, one column per number.

ʰc̲ols ← { x →
  '∨ r̲/ r̲avel x < 0 ? @ p̲anic< "Bits works on whole numbers 0 or more, not {x}"
  (w r̲eshape 2) e̲ncode x
}

p̲anic< expands to

(⎕P̲ANIC ("Bits works on whole numbers 0 or more, not " c̲at (f̲ormat (x))))

Used in: ˡp̲opcount, ˡa̲nd, ˡo̲r, ˡx̲or, ˡu̲ngray

ˡb̲its : Int -> Int -> Int

function · line 25

n b_its x: the low n bits of each number, most significant first: a vector for one number, a row per number for several.

ˡb̲its ← { n x →
  '∨ r̲/ r̲avel x < 0 ? @ p̲anic< "Bits works on whole numbers 0 or more, not {x}"
  o̲\ (n r̲eshape 2) e̲ncode x
}

p̲anic< expands to

(⎕P̲ANIC ("Bits works on whole numbers 0 or more, not " c̲at (f̲ormat (x))))

Used in: libs/Bits/demos/nim.xtl:20, libs/Bits/demos/record.xtl:15

ˡv̲alue : Num a => a -> a

function · line 31

v_alue bits: the number each row of bits (or the vector) stands for.

ˡv̲alue ← { bits → 2 d̲ecode o̲\ bits }

Bit by bit

ˡp̲opcount : Int -> Int

function · line 36

p_opcount x: how many 1 bits each number has.

ˡp̲opcount ← { x → '+ r̲/ ʰc̲ols x }

ˡa̲nd : Int -> Int -> Int

function · line 44

a a_nd b, a o_r b, a x_or b: bit by bit, item by item (a single number on either side goes with every item of the other: a + 0 * b has the shape of both). On 0/1 digits: and is the smaller, or the larger, xor the distance; Int arithmetic keeps the result an Int (a comparison such as & would leave its numeric type to the caller: ask X17).

ˡa̲nd ← { a b → 2 d̲ecode (ʰc̲ols a + 0 × b) m̲in ʰc̲ols b + 0 × a }

ˡo̲r : Int -> Int -> Int

function · line 45

ˡo̲r ← { a b → 2 d̲ecode (ʰc̲ols a + 0 × b) m̲ax ʰc̲ols b + 0 × a }

ˡx̲or : Int -> Int -> Int

function · line 46

ˡx̲or ← { a b → 2 d̲ecode a̲bs (ʰc̲ols a + 0 × b) − ʰc̲ols b + 0 × a }

Used in: ˡg̲ray, nimsum, target, libs/Bits/demos/nim.xtl:21

Shifts and masks

ˡs̲hl : Num a => a -> a -> a

function · line 52

n s_hl x, n s_hr x: each number shifted n bits left (times 2^n) or right (halved n times, dropping the bits shifted out).

ˡs̲hl ← { n x → x × 2 ^ n }

ˡs̲hr : Int -> Int -> Int

function · line 53

ˡs̲hr ← { n x → x d̲iv 2 ^ n }

Used in: ˡg̲ray

ˡb̲it? : Truthy a => Int -> Int -> a

function · line 56

i b_it? x: whether bit i of each number is 1.

ˡb̲it? ← { i x → 1 = (x d̲iv 2 ^ i) m̲od 2 }

ˡm̲ask : Num a => a -> a

function · line 59

m_ask n: the number whose low n bits are 1.

ˡm̲ask ← { n → (2 ^ n) − 1 }

Gray code

ˡg̲ray : Int -> Int

function · line 65

g_ray x: the Gray code of each number (neighbors differ in one bit); u_ngray g: back again.

ˡg̲ray ← { x → x ˡx̲or 1 ˡs̲hr x }

ˡu̲ngray : Int -> Int

function · line 66

ˡu̲ngray ← { g → 2 d̲ecode '≠ s̲\ ʰc̲ols g }