import math ; ilog, pow import util ; digits
; The bitwise operators all work very similarly, differing only in how they ; map pairs of bits to 0 or 1. For AND, we simply multiply them. For OR, we ; sum them, add 1, then divide by 2. For XOR, we only want 1 if they're neq. ; We repeatedly halve the inputs while consuming bits and stop when at least ; one of them becomes zero. For AND, the answer is in the accumulator and we ; are done. For OR and XOR, it's likely the nonzero input still has bits to ; contribute, so we also accumulate its product with the current power of 2. $bitfun(op, bit, done) { push -2,1,-1,0 store store _`op`_loop: push -1
copy 2 push 2 mod copy 2 push 2 mod `bit` @-1 swap @-2 dup push 2 mul ^-2 mul add store push 2 div swap push 2 div dup copy 2 mul jz _`op`_done swap jump _`op`_loop
_`op`_done: `done` ret }
; returns the bitwise AND of A and B ; [A B] => [A & B] ; ; [65 47] => [1] [83 25] => [17] ; [40 64] => [0] [74 59] => [10] ; [31 18] => [18] [86 32] => [0] ; [93 79] => [77] [11 79] => [11] band: $bitfun(band, mul, mul $– load)
; returns the bitwise OR of A and B ; [A B] => [A | B] ; ; [66 51] => [115] [64 4] => [68] ; [61 77] => [125] [93 65] => [93] ; [14 87] => [95] [71 37] => [103] ; [7 19] => [23] [38 92] => [126] bor: $bitfun(bor, add $++ push 2 div, add @-2 mul @-1 add)
; returns the bitwise XOR of A and B ; [A B] => [A ^ B] ; ; [4 14] => [10] [0 80] => [80] ; [51 5] => [54] [97 77] => [44] ; [39 65] => [102] [12 26] => [22] ; [44 36] => [8] [6 21] => [19] bxor: $bitfun(bxor, :neq, add @-2 mul @-1 add)
; returns the infinite-precision bitwise NOT of N by inverting all of its bits ; [N] => [~N] ; ; [58] => [5] [46] => [17] ; [48] => [15] [87] => [40] ; [98] => [29] [51] => [12] ; [3] => [0] [42] => [21] bnot:
dup push 0 swap push 1 add sub swap push 2 :ilog push 2 swap :pow mod ret
; returns the number of bits in the binary representation of N ; [N] => [# of bits] ; ; [0] => [0] [1] => [1] ; [7] => [3] [8] => [4] ; [255] => [8] blength: dup jz _blength_zero push 2 :ilog $++ ret _blength_zero: ret
; returns the number of set bits in N ; [N] => [popcount] ; ; [0] => [0] [1] => [1] ; [7] => [3] [8] => [1] popcount: push 0 _popcount_loop:
copy 1 push 2 mod add swap push 2 div dup jz _popcount_done swap jump _popcount_loop
_popcount_done: pop ret