| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
I have two integers A and B, and another two C and D. I'd like to find a very simple function f such that f(A) = C and f(B) = D. This simple function will be implemented with arithmetic addition and subtraction, bit-wise logical operations, logical shifts and any necessary constants (which would be pre-computed from A, B, C, and D). The fewer operations, the better. How can it be done?
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 702.1 | BEING::POSTPISCHIL | Always mount a scratch monkey. | Fri May 08 1987 13:26 | 5 | |
I can guarantee five or fewer operations, given a two's complement
machine.
-- edp
| |||||
| 702.2 | not so simple | VINO::JMUNZER | Fri May 08 1987 13:28 | 28 | |
Pick some bit 2^k that's different in A and B. Let Rk (x) be a k-bit right
shift of x (zero-filled).
f(x) = AND (0 - Rk ( AND ( XOR (x, B), 2^k) ), C) +
AND (0 - Rk ( AND ( XOR (x, A), 2^k) ), D)
Then:
f(A) = AND (0 - Rk ( AND ( XOR (A, B), 2^k) ), C) +
AND (0 - Rk ( AND ( XOR (A, A), 2^k) ), D)
= AND (0 - Rk ( AND ( 2^k + other bits, 2^k) ), C) +
AND (0 - Rk ( AND (0, 2^k) ), D)
= AND (0 - Rk (2^k), C) +
AND (0 - Rk (0), D)
= AND (0 - 1, C) +
AND (0 - 0, D)
= AND (-1, C) +
AND (0, D)
= C
[assuming twos complement arithmetic]
John
| |||||
| 702.3 | SSDEVO::LARY | Sun May 10 1987 03:58 | 11 | ||
Even fewer operations would be: (using the notation of .-1): f(x) = AND (0 - AND ( Rk(x), 1), DIFF) + BASE Where BASE and DIFF are pre-computed constants with the values: BASE = C and DIFF = D-C if bit 2^k is set in B but not in A BASE = D and DIFF = C-D if bit 2^k is set in A but not in B | |||||