calc: Binary Functions
8.7 Binary Number Functions
===========================
The commands in this chapter all use two-letter sequences beginning with
the ‘b’ prefix.
The “binary” operations actually work regardless of the currently
displayed radix, although their results make the most sense in a radix
like 2, 8, or 16 (as obtained by the ‘d 2’, ‘d 8’, or ‘d 6’ commands,
respectively). You may also wish to enable display of leading zeros
with ‘d z’. Radix Modes.
The Calculator maintains a current “word size” ‘w’, an arbitrary
positive or negative integer. For a positive word size, all of the
binary operations described here operate modulo ‘2^w’. In particular,
negative arguments are converted to positive integers modulo ‘2^w’ by
all binary functions.
If the word size is negative, binary operations produce
twos-complement integers from ‘-(2^(-w-1))’ to ‘2^(-w-1)-1’ inclusive.
Either mode accepts inputs in any range; the sign of ‘w’ affects only
the results produced.
The ‘b c’ (‘calc-clip’) [‘clip’] command can be used to clip a number
by reducing it modulo ‘2^w’. The commands described in this chapter
automatically clip their results to the current word size. Note that
other operations like addition do not use the current word size, since
integer addition generally is not “binary.” (However,
Simplification Modes, ‘calc-bin-simplify-mode’.) For example, with a
word size of 8 bits ‘b c’ converts a number to the range 0 to 255; with
a word size of -8 ‘b c’ converts to the range -128 to 127.
The default word size is 32 bits. All operations except the shifts
and rotates allow you to specify a different word size for that one
operation by giving a numeric prefix argument: ‘C-u 8 b c’ clips the top
of stack to the range 0 to 255 regardless of the current word size. To
set the word size permanently, use ‘b w’ (‘calc-word-size’). This
command displays a prompt with the current word size; press <RET>
immediately to keep this word size, or type a new word size at the
prompt.
When the binary operations are written in symbolic form, they take an
optional second (or third) word-size parameter. When a formula like
‘and(a,b)’ is finally evaluated, the word size current at that time will
be used, but when ‘and(a,b,-8)’ is evaluated, a word size of -8 will
always be used. A symbolic binary function will be left in symbolic
form unless the all of its argument(s) are integers or integer-valued
floats.
If either or both arguments are modulo forms for which ‘M’ is a power
of two, that power of two is taken as the word size unless a numeric
prefix argument overrides it. The current word size is never consulted
when modulo-power-of-two forms are involved.
The ‘b a’ (‘calc-and’) [‘and’] command computes the bitwise AND of
the two numbers on the top of the stack. In other words, for each of
the ‘w’ binary digits of the two numbers (pairwise), the corresponding
bit of the result is 1 if and only if both input bits are 1:
‘and(2#1100, 2#1010) = 2#1000’.
The ‘b o’ (‘calc-or’) [‘or’] command computes the bitwise inclusive
OR of two numbers. A bit is 1 if either of the input bits, or both, are
1: ‘or(2#1100, 2#1010) = 2#1110’.
The ‘b x’ (‘calc-xor’) [‘xor’] command computes the bitwise exclusive
OR of two numbers. A bit is 1 if exactly one of the input bits is 1:
‘xor(2#1100, 2#1010) = 2#0110’.
The ‘b d’ (‘calc-diff’) [‘diff’] command computes the bitwise
difference of two numbers; this is defined by ‘diff(a,b) =
and(a,not(b))’, so that ‘diff(2#1100, 2#1010) = 2#0100’.
The ‘b n’ (‘calc-not’) [‘not’] command computes the bitwise NOT of a
number. A bit is 1 if the input bit is 0 and vice-versa.
The ‘b l’ (‘calc-lshift-binary’) [‘lsh’] command shifts a number left
by one bit, or by the number of bits specified in the numeric prefix
argument. A negative prefix argument performs a logical right shift, in
which zeros are shifted in on the left. In symbolic form, ‘lsh(a)’ is
short for ‘lsh(a,1)’, which in turn is short for ‘lsh(a,n,w)’. Bits
shifted “off the end,” according to the current word size, are lost.
The ‘H b l’ command also does a left shift, but it takes two
arguments from the stack (the value to shift, and, at top-of-stack, the
number of bits to shift). This version interprets the prefix argument
just like the regular binary operations, i.e., as a word size. The
Hyperbolic flag has a similar effect on the rest of the binary shift and
rotate commands.
The ‘b r’ (‘calc-rshift-binary’) [‘rsh’] command shifts a number
right by one bit, or by the number of bits specified in the numeric
prefix argument: ‘rsh(a,n) = lsh(a,-n)’.
The ‘b L’ (‘calc-lshift-arith’) [‘ash’] command shifts a number left.
It is analogous to ‘lsh’, except that if the shift is rightward (the
prefix argument is negative), an arithmetic shift is performed as
described below.
The ‘b R’ (‘calc-rshift-arith’) [‘rash’] command performs an
“arithmetic” shift to the right, in which the leftmost bit (according to
the current word size) is duplicated rather than shifting in zeros.
This corresponds to dividing by a power of two where the input is
interpreted as a signed, twos-complement number. (The distinction
between the ‘rsh’ and ‘rash’ operations is totally independent from
whether the word size is positive or negative.) With a negative prefix
argument, this performs a standard left shift.
The ‘b t’ (‘calc-rotate-binary’) [‘rot’] command rotates a number one
bit to the left. The leftmost bit (according to the current word size)
is dropped off the left and shifted in on the right. With a numeric
prefix argument, the number is rotated that many bits to the left or
right.
Set Operations, for the ‘b p’ and ‘b u’ commands that pack
and unpack binary integers into sets. (For example, ‘b u’ unpacks the
number ‘2#11001’ to the set of bit-numbers ‘[0, 3, 4]’.) Type ‘b u V #’
to count the number of “1” bits in a binary integer.
Another interesting use of the set representation of binary integers
is to reverse the bits in, say, a 32-bit integer. Type ‘b u’ to unpack;
type ‘31 <TAB> -’ to replace each bit-number in the set with 31 minus
that bit-number; type ‘b p’ to pack the set back into a binary integer.