Saturday, February 4, 2023

Bitwise operations without bitwise operators

JsFiddle: See the code in action, in neat & orderly JavaScript



It was a fun little programming exercise to achieve bitwise operations with non-bitwise operators.

Rules: I only want to use functions (and therefore loops (recursive)), logic, addition, subtraction, multiplication, and division (and therefore modulus and exponents)

flip all bits in a byte:
var flipMe = 255 - flipMe; // flipMe = ~flipMe;

shift byte left by 2 bits:
var shiftMe = 3; // 0000 0011
var nob = 2; // Number Of Bits (to shift)
shiftMe *= Math.pow(2 * nob); // 0000 1100. or shiftMe = shiftMe << 2;
// to shift right: shiftMe /= 2*nob;
// IMO Math.pow() is not cheating, as we could recreate it with a for() loop


bitwise AND
var randValue = 178; // 1011 0010
var bwAnd = 35; // value we want to check if it matches. 0010 0011
function getBitArray(num){ // get array of bits without bitwise (use mod, IMO not cheating)
    var ary = [];
    var lastNum = 0;
    for(var xint = 1;xint < 9;xint++){ // mod 2^1 through 2^256
        var newNum = num % (Math.pow(2,xint));
        // if the number is different, there was a bit representing the relevant power of 2
        if(newNum != lastNum){
            ary.push(1);
            lastNum = newNum;
        }else{
            ary.push(0);
        }
    }
    return ary; // index 0 is the low order bit
}
// now that we have the bit array, just compare bytes and create a number with proper bits
var result = 0; // 0000 0000
for() each bit
    if(bit in randValue matches bit in bwAnd and the bit is 1)
        result += bwShiftLeft() by [which bit this is] // we shift with our function
// this was a tough one. The most eloquent solution I could think of is using logic and modulo (%) to get the individual bits, which to me is just a glorified while() loop of subtraction for our purposes and therefore isn't cheating IMO.
// If you want to rule out the modulo, we might have to use above bit shifting to achieve this: bit 1 would be ((randValue << 7) >> 7).


bitwise OR & bitwise XOR
the same as bitwiseAnd but with changes for OR/XOR when deciding whether to add a shifted bit

change bit values (obvious one): turn bit 2 from 1 to 0
var randValue = 10; // 0000 1010
randValue = randValue - 2; // now 0000 1000
// or change bit 1 from 0 to 1
randValue = randValue + 1; // now 0000 1001
// Note: of course won't work if the bit is not as anticipated.
// If we randValue-1 when bit 1 is already 0, it will still subtract like normal, changing the other bits in the process.
// Should check if the bit is as anticipated first.

if((randValue % 2) == 1) randValue -= 1;

No comments:

Post a Comment

Coding Challenge #54 C++ int to std::string (no stringstream or to_string())

Gets a string from an integer (ejemplo gratis: 123 -> "123") Wanted to come up with my own function for this like 10 years ago ...