Bit manipulation of large numbers in pl/sql

As I mentioned in my previous post I had to write my own functions to perform some bit operations on numeric values. While looking into some other pseudo-random number generators I ran into a few unexpected problems.

The first problem is actually a documented restriction; but one I had not encountered previously. The BITAND function only supports numbers up to 2¹²⁷-1. For most real-world numbers that isn’t an issue; but in my current project I found myself working with 128-bit values occasionally and I would get an error with BITAND, even if the result would be smaller (requiring only 64 bits,) it didn’t matter. If either input is too large, the function failed.

SQL> SELECT bitand(217233078327773927912690501856593925887, POWER(2, 64) - 1) FROM DUAL;
SELECT bitand(217233078327773927912690501856593925887, POWER(2, 64) - 1) FROM DUAL
       *
ERROR at line 1:
ORA-01426: numeric overflow
Help: https://docs.oracle.com/error-help/db/ora-01426/

Or, in PL/SQL

SQL> begin
  2  dbms_output.put_line(bitand(217233078327773927912690501856593925887, POWER(2, 64) - 1));
  3  end;
  4  /
begin
*
ERROR at line 1:
ORA-06502: PL/SQL: numeric or value error
ORA-06512: at line 2
Help: https://docs.oracle.com/error-help/db/ora-06502/

So, once I discovered the upper limit, I decided I would just have to write my own function using division and MOD function to shift bits around. My thought process was shift both values one bit to the right (i.e. divide the values by 2.) The shifted value would then be within valid range of the native BITAND. Then shift that result back to the left one bit (i.e. multiply it by 2.) All that is left is checking the 1-bit in each number, and if both are 1 then add 1, if not, then add 0 (i.e. manually ANDing the values and putting the result in the 1-bit position.

This seemed simple enough, but I ran into two issues. In order to extract the first bit of the value, I would normally use BITAND, but I can’t. This is where MOD comes in. I divide the value with modulo 2 and keep the remainder. If it’s odd (i.e. has 1 in the first bit) the remainder will be 1, if it’s even (i.e. has 0 in the first bit) then the remainder will be 0.
BUT, it turns out that MOD doesn’t work correctly for some large numbers. For some values, a remainder of 1 will instead be returned as -1.

SQL> select mod(217233078327773927912690501856593925887,2) from dual;

MOD(217233078327773927912690501856593925887,2)
----------------------------------------------
                                            -1

Fortunately, since I’m using MOD 2, I don’t need to check a myriad of possible remainder values – they will be either 0, 1, or in these odd cases, -1. It’s a bit of a hack; but I can check for -1 and if I find it, change the result to 1 as it should be.

However, the problem doesn’t end there. When MOD doesn’t work, as you might expect, division doesn’t work reliably either. Odd numbers do not divide correctly. The 0.5 remainder from dividing by 2 is not returned. Instead, the quotient is returned rounded up. Using FLOOR doesn’t help because the division is returning an integer value (the wrong value) so FLOOR simply returns the value itself.

SQL> select 217233078327773927912690501856593925887/2 from dual;

217233078327773927912690501856593925887/2
-----------------------------------------
  108616539163886963956345250928296962944

SQL> select FLOOR(217233078327773927912690501856593925887/2) from dual;

FLOOR(217233078327773927912690501856593925887/2)
------------------------------------------------
         108616539163886963956345250928296962944

So, that means when I do my shift-right, division by 2, I need to account for this error as well. Thus, when I check if my MOD results are erroneous, I also correct the corresponding bit-shifting division result.

v_a_first_bit := MOD(p_a, 2);
v_b_first_bit := MOD(p_b, 2);

-- for large numbers, MOD can fail and return -1 instead of 1, so check for that.
-- when MOD fails that also means division fails
IF v_a_first_bit = -1
THEN
    v_a_first_bit := 1;
    v_a_shift := FLOOR(p_a / 2) - 1;
ELSE
    v_a_shift := FLOOR(p_a / 2);
END IF;

IF v_b_first_bit = -1
THEN
    v_b_first_bit := 1;
    v_b_shift := FLOOR(p_b / 2) - 1;
ELSE
    v_b_shift := FLOOR(p_b / 2);
END IF;

Pulling all of this together, my function only follows these steps when processing large values (i.e. greater than or equal to 2¹²⁷.) For smaller values, I simply use the native function for simplicity and efficiency.

The final function then is:

CREATE OR REPLACE FUNCTION big_bitand(p_a IN NUMBER, p_b IN NUMBER)
    RETURN NUMBER
IS
    v_result       NUMBER;
    v_temp         NUMBER;
    v_a_shift      NUMBER;
    v_b_shift      NUMBER;
    v_a_first_bit   NUMBER;
    v_b_first_bit   NUMBER;
BEGIN
    -- Oracle's native BITAND  function has an upper limit of power(2,127)-1
    CASE
        WHEN p_a < POWER(2, 127) AND p_b < POWER(2, 127)
        THEN
            v_result := BITAND(p_a, p_b);
        ELSE
            -- Divide by 2 (shift right by 1 bit) to put the values in range
            -- BITAND the reduced values, and then shift back left by multiplying by 2.
            -- Then add the 1-bit that was dropped off by shifting right.
            -- Since we can't use bitand, we have to use modulo division to find the 1-bit value.

            v_a_first_bit := MOD(p_a, 2);
            v_b_first_bit := MOD(p_b, 2);

            -- for large numbers, MOD can fail and return -1 instead of 1, so check for that.
            -- when MOD fails that also means division fails
            IF v_a_first_bit = -1
            THEN
                v_a_first_bit := 1;
                v_a_shift := FLOOR(p_a / 2) - 1;
            ELSE
                v_a_shift := FLOOR(p_a / 2);
            END IF;

            IF v_b_first_bit = -1
            THEN
                v_b_first_bit := 1;
                v_b_shift := FLOOR(p_b / 2) - 1;
            ELSE
                v_b_shift := FLOOR(p_b / 2);
            END IF;

            v_temp := BITAND(v_a_shift, v_b_shift) * 2;

            v_result := v_temp + CASE WHEN v_a_first_bit = 1 AND v_b_first_bit = 1 THEN 1 ELSE 0 END;
    END CASE;

    RETURN v_result;
END big_bitand;

One last quirk that, in hindsight, might have been obvious is that I originally wrote the function using INTEGER for the parameter and variable data types. I was only working with non-negative integer values, so it seemed like a logical choice. However, the INTEGER subtype is defined as NUMBER(38,0) which is too small to hold the large values I'm targeting. So, I had to go with an unconstrained NUMBER.

Testing with my large value trying to mask off the lower 64 bits is now possible.

SQL> SELECT big_bitand(217233078327773927912690501856593925887, POWER(2, 64) - 1) FROM DUAL;

BIG_BITAND(217233078327773927912690501856593925887,POWER(2,64)-1)
-----------------------------------------------------------------
                                              8423715553069717247

While the final code is not that complex, I spent a long time pulling my hair out trying to figure out why I needed to jump through those hoops. Also, unlike the limit for BITAND, MOD and division don't have similar limitations documented, or if they do, I couldn't find the limits anywhere, so I suppose these could be considered bugs.

Now that I have this in my toolbox, I can move forward with the rest of my PRNG project. I hope you found this interesting and helpful. Questions and comments, as always, are welcome.