TECHNIQUE: BITWISE OPERATIONS
After interpretation of the statement V="A" we can see the contents of the V variable by the simple statement say V. It displays A on the screen. The value "A" is saved in one byte as a sequence bits. We display this sequence by the Rexx say X2B(C2X(V)) statement. The statement say C2X(V) will show the hexadecimal representation. And the C2D(V) function returns the value of V interpreted as a decimal number, for our example and ASCII it is 65 (16*4+1).
List of implementations of bitwise operations
The BITAND function is bitwise AND operation, it returns its operators ANDed together bit by bit.
The BITOR function is bitwise OR operation, it returns its operators ORed together bit by bit.
The BITXOR function is bitwise eXclusive OR (XOR) operation, it returns its operators XORed together bit by bit.
Bitwise left shift by B bits for N is equal
B must be nonnegative.
Bitwise rigth shift by B bits for N is equal
B must be nonnegative.
EXAMPLE 1 - Vernam's method
The BITXOR function is as well the famous Vernam's encryption and decryption method. To encrypt a message Text, using Vernam's method, proceed as follows. First, create random string of bits Key, where LENGTH(Text)=LENGTH(Key). Then encrypt the Text by
To decrypt the ciphertext perform
Then Text==Plaintext. You can try the following program.
/* VERNAM */
parse arg Text
L = LENGTH(Text) * 8; Key = ""
do J = 1 to L
Key = Key || RANDOM(0, 1)
Key = X2C(B2X(Key))
Ciphertext = BITXOR(Text, Key)
Plaintext = BITXOR(Ciphertext, Key)
if Plaintext == Text
then say "Vernam's method works"
else say "Eh?"
EXAMPLE 2 - Gray code
Gray code is a function G of the integers I, that for each integer N>=0 is one-to-one for
and that has the following property: The binary representation of G(I)
, for Ip1=I+1
, differ in exactly one bit.
The algorithm for generating this code is simply to form the bitwise exclusive-or (BITXOR) of I and I%2, where I%2 is bitwise right shift by 1 bit.
The following program GRAY displays on the screen, for the argument equals 15
00000000 00000001 00000011 00000010 00000110 00000111 00000101 00000100 00001100 00001101 00001111 00001110 00001010 00001011 00001001 00001000
We need to know the number of bits necessary to represent the codes plus the padding to align to nearest byte boundary. The number of bits of the N-th code is
The BYTES function returns the necessary number of bytes for a given number of bits.
/* GRAY_CODE */
parse arg N
S = BYTES(LENGTH(X2B(D2X(N))))
Gray_code = ""
do I = 0 to N
Ibrs1 = I % 2
A = D2C(I, S); B = D2C(Ibrs1, S)
C = BITXOR(A, B)
Gray_code = Gray_code X2B(C2X(C))
parse arg B
R = B // 8
if R <> 0 then B = B + 8 - R
return B % 8
EXAMPLE 3 - Decompression routine
The input for this routine is a compressed text C. It contains two types codewords - LITERAL X and COPY X, -Y.
means pass the next X characters directly into the uncompressed output D.
means go back Y
characters in the uncompressed output and copy X
characters forward to the current position.
We will use 8 bits for coding a LITERAL codeword and 16 bits for coding a COPY codeword. If the first 4 bits are 0, then the codeword is a literal; the next 4 bits encode the length X in the range 1 to 16 (0 to 15 in code) and the following X characters are literal. Otherwise, the codeword is a copy; the first 4 bits encode a length X in range 3 to 17 (1 to 16 in code) and the next 12 bits are a displacement Y in the range 1 to 4096 (0 to 4095 in code).
The input string AAAAAABBBBCCCAABBBBC with 20 characters can be compressed into the string
'00'X || "A" ||, /* literal */
'3000'X || , /* copy */
'00'X || "B" || , /* literal */
'1000'X || , /* copy */
'02'X || "CCC" || , /* literal */
with 14 characters.
parse arg C
D = ""; LengthC = LENGTH(C); Pc = 1; Pd = 1
do while Pc < LengthC
Byte = SUBSTR(C, Pc, 1)
if BITOR(Byte, '0F'X) = '0F'X
then call LITERAL Byte
else call COPY Byte
LITERAL: procedure expose C D Pc Pd
parse arg L
L = C2D(L) + 1
D = D || SUBSTR(C, Pc + 1, L)
Pc = Pc + L + 1
Pd = Pd + L
COPY: procedure expose C D Pc Pd
parse arg L
L1 = C2D(L) % 16 + 2; L = L1
X = C2D(BITAND('0FFF'X, SUBSTR(C, Pc, 2))) + 1
Y = Pd - X
do while L > X
D = D || SUBSTR(D, Y, X)
L = L - X
X = 2 * X
if L > 0 then D = D || SUBSTR(D, Y, L)
Pc = Pc + 2; Pd = Pd + L1
Fiala E.R., Greene D.H., Data Compression with Finite Windows
CACM, April 1989, Vol. 32, No. 4, pp. 490-505
Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P., Numerical Recipes in C : the art of scientific computing
- 2nd ed. University Press, Cambridge, 1992