(49g 50g) Logic Operations for Large Integers

[John Keith]

Most computer algebra systems and some newer programming languages have the ability to perform bit-level logic operations (AND, OR, XOR) on integers of any size. On HP RPL calculators, these operations are only available for binary numbers (beginning with #). Numbers less than 10^12 (or about 10^18 with Joe Horn's B->I and I->B) can be converted to binary numbers and back but this is not possible for larger integers.

The solution that I came up with was inspired by these threads by member GeraldH. It is possible because bit-level logic operations also work on strings, which are represented in memory as arrays of 8-bit integers. The programs use base and string commands from the ListExt library. They can be used with any integer that will fit in memory, potentially thousands of digits.

The first program I→S (I\->S with trigraphs) converts an integer (exact or approximate) into a string.

Code:


\<< 256 I\->BL NL\->S
\>>

Note that the resulting string may contain character 0 and thus cannot be edited.

The inverse operation S→I (S\->I) converts a string into an exact integer.

Code:


\<< S\->NL 256 BL\->I
\>>

Performing logic operations on strings requires that both strings be the same length. This necessitates the rather large and clunky program below which I call BITINT. The program tests the lengths of the strings and if they are not the same, pads the short string on the left with 0 characters.

To use the program, the two integers should be on levels 2 and 3, and a logical operation on level 1. The logical operation can be a program, list or null-tagged command.

Code:


\<< UNROT I\->S SWAP I\->S           @ Convert both integers to strings
 DUP2 SIZE SWAP SIZE
  IF DUP2 SAME
  THEN DROP2                         @ Skip to END if same size
  ELSE - UNROT PICK3 0. >
   :: SWAP IFT                       @ Ensure shortest string on level 1
   ROT ABS 0. CHR SWAP RPTCHR SWAP + @ Pad left with 0 characters
  END ROT EVAL S\->I                 @ Evaluate program and convert
\>>                                  @ to integer

For example,

123456
789
:: XOR BITINT

-> 123221

Logical NOT is more problematic because NOT applies to all bits in a word, so 1 I\->S NOT S\->I returns 254, not 0. Using binary numbers (e.g. # 3Fh), the result is a negative number that is dependent on word size. To invert the significant bits of a number without regard to word size, the following short program can be used.

Code:


\<< 2 I\->BL 1 SWAP - 2 BL\->I
\>>