2

I hope someone has some experience with left shift (<<) and 2's Complement in SSJS and can help me to confirm my assumption and suggest a better approach for that problem.

Assumption

  1. SSJS is not using 2's Complement resulting in Arithmetic operation overflow when dealing with negative numbers.
  2. SSJS left shift operator << is using the logical approach of x * ( 2 ** y ) irrespectively of a 32 bit size. This results in a larger number as there are no excess bits and it will continue to shift with zeros from the right.

Question

  1. How can I overcome the missing 2's Complement in SSJS?
  2. Is there a way to limit the size of the shift to 32 bit in SSJS?
  3. My sample code below works but I am interested if there is a better solution.

Deep dive

I believe I understand how shifting bits in a signed 32 bit integer works but there are still a few grey areas so please be gentle if anything below is not accurate.

Shifting the current bits to the left by the specific number of bits. Excess bits shifted off to the left are discarded. Zero bits are shifted in from the right.

<script runat="server">
    Platform.Load("Core", "1.1.5");
   
    var i = 1073741824,
        i_bit = i.toString(2); // 0100 0000 0000 0000 0000 0000 0000 0000
    
    // shifting i by 1 bit to the left
    var i_shifted = (i << 1); // 2147483648
        i_shifted_bit = i_shifted.toString(2); // 1000 0000 0000 0000 0000 0000 0000 0000 
    
    Write(i+'<br/>');
    Write(i_bit+'<br/>');
    Write(i_shifted+'<br/>');
    Write(i_shifted_bit+'<br/>');
</script>

Here is the first difference between SSJS and JS. JS is using 2's Complement and uses the last position as a negative indicator. This seems to be different in SSJS as it does not allow negative numbers for shifting at all.

SSJS:
 268435456 |   16777216 |   1048576 | 65536 | 4096 |  256 |   16 |    1 (32 bit)
      1... |       0... |      0... |  0... | 0... | 0... | 0... | ...0 = 268435456

JS Shifting with 2's Complement is using the highest bit as -:
-268435456 |   16777216 |   1048576 | 65536 | 4096 |  256 |   16 |    1 (32 bit)
      1... |       0... |      0... |  0... | 0... | 0... | 0... | ...0 = -268435456

If you try -1 << 1 in JS your result will be -2. In SSJS this throws an Arithmetic operation overflow Error.


The other difference is that the left shift operator (<<) yields different results in SSJS than in JS. I assume it is just a quick implementation of the algorithm x * ( 2 ** y ). This results that the excess bits are not dropped but the number is extended beyond the 32 bit integer.

This will not allow me to convert the integer into a binary string as it exceed the allowance of Uint32.

<script runat="server">
    Platform.Load("Core", "1.1.5");
   
    var i = 1073741824,
        i_bit = i.toString(2); // 0100 0000 0000 0000 0000 0000 0000 0000
    
    // shifting i by 1 bit to the left
    var i_shifted = (i << 2) // 4294967296
        // System.OverflowException: Value was either too large or too small for a UInt32
        // i_shifted_bit = i_shifted.toString(2); // 0001 0000 0000 0000 0000 0000 0000 0000 0000 
    
    Write(i+'<br/>');
    Write(i_bit+'<br/>');
    Write(i_shifted+'<br/>');
    Write(i_shifted_bit+'<br/>');
</script>

The expected value is 0 and not 4294967296 as the leading 01 is shifted out of the 32 bit window as we define a left shift of 2.

My take to solve this

As mentioned above, I was wondering if there is a better way of solving this in SSJS. Here is my code:

<script runat="server">
    Platform.Load("Core", "1.1.5");
 
    try {

       function leftShift(a,b) { 
            var d = a<<b,
                r = [],
                i = 0,
                n = (d<0)?true:false;

            d = (n)?d*-1:d
            if ( d == 0) {
              return 0;
            }


            // Decimal integers to binary: Algorithm
            // Step 1. Divide the integer by 2, while noting the quotient and remainder.
            // Step 2. Then, divide the quotient again by 2, and record the 3rd quotient and remainder.
            // Step 3. Like this, keep dividing each successive quotient by 2 until you get a quotient of zero.
            // Step 4. After this, just write all the remainders in reverse order to get the binary representation of the integer.
            while (d !== 0) {
                r[i++] = (d % 2); // store remainder
                d = Math.floor(d/2); // store quotient
            }

            // if it exceed 32 drop the overflow
            if (r.length > 32) {
                r = r.slice(0,32)
            }

            // reverse the binary array join each element and parseInt
            r = parseInt(r.reverse().join(''), 2);

            return (n)?-1*r:r;
        }


        Write(leftShift(1073741824,1)+'<br/>'); // -2147483648
        Write(leftShift(1073741824,2)+'<br/>'); // 0
        Write(leftShift(5,3)+'<br/>'); // 20
        Write(leftShift(-1,1)+'<br/>'); // -2

    } catch(e) {
        Write(e)
    }
</script>
2
  • 2
    What kind SFMC solution involves fiddling with bits? Dec 1, 2021 at 13:46
  • Involves SHA256 but will share when finished as usual
    – shd.lux
    Dec 1, 2021 at 13:58

1 Answer 1

0

The code from my question had many flaws and it took me a while to get a better working version. The following code has been tested against 20 000 iterations of different positive and negative shifts.

There is a possability that it can yield a different result and I am keen to see if anyone has a better / simpler solution to enable left shift in SSJS with 2s Complement and negative numbers.

<script runat="server">
    Platform.Load("Core", "1.1.5");

    var util = {};

    util.findTwoscomplement = function(str) {
        var n = str.length;

        // Traverse the string to get first '1' from the last of string
        var i;
        for (i = n - 1; i >= 0; i--)
            if (str.charAt(i) == '1')
                break;

        // If there exists no '1' concat 1 at the starting of string
        if (i == -1)
            return "1" + str;

        // Continue traversal after the position of first '1'
        for (k = i - 1; k >= 0; k--) {
            // Just flip the values
            if (str.charAt(k) == '1')
                str = str.substring(0, k) + "0" + str.substring(k + 1, str.length);
            else
                str = str.substring(0, k) + "1" + str.substring(k + 1, str.length);
        }

        // return the modified string
        return str.toString();
    }

    util.decimalToBinary = function(d) {
        var i = 0,
            r = [], // store the result
            n = (d < 0) ? true : false; // if negative we use ceil otherwise floor for compute

        // Decimal integers to binary: Algorithm
        // Step 1. Divide the integer by 2, while noting the quotient and remainder.
        // Step 2. Then, divide the quotient again by 2, and record the 3rd quotient and remainder.
        // Step 3. Like this, keep dividing each successive quotient by 2 until you get a quotient of zero.
        // Step 4. After this, just write all the remainders in reverse order to get the binary representation of the integer.
        while (d !== 0) {
            r[i++] = (n) ? -1 * (d % 2) : (d % 2); // store remainder
            d = (n) ? Math.ceil(d / 2) : Math.floor(d / 2); // store quotient
        }

        // reverse to get the actual binary value
        r = r.reverse().join('');

        // if decimal was positive we can just pad an return otherwise convert to 2s complement
        if (!n) {
            return r.padStart(32, '0');
        } else {
            return util.findTwoscomplement(r).padStart(32, '1');
        }
    }

    util.binaryToDecimal = function(b) {
        var a = Array.from(b),
            r = 0;

        for (var i = 0; i < a.length; i++) {
            var v = Number(a[i]) * Math.pow(2, (31 - i))
            r = (i == 0) ? r - v : r + v;
        }
        return r;
    };

    util.leftShift = function(a, b) {
        // only shift a maximum of 32 bits
        var b = b % 32;

        // convert a to binary
        a = util.decimalToBinary(a);

        // pad from the right with the length of b
        a = a.padEnd((b + a.length), '0');

        // only take the last 32 bits
        a = a.substr(a.length - 32, a.length);

        // convert binary to decimal with 2s complement
        return util.binaryToDecimal(a);
    };




    ///////////////////////////////////////////////////////////////////////
    //////////////////////////////           //////////////////////////////
    ////////////////////////////// POLYFILLS ////////////////////////////// 
    //////////////////////////////           //////////////////////////////
    ///////////////////////////////////////////////////////////////////////

    // ECMAScript (ECMA-262)
    Number.isInteger = Number.isInteger || function(value) {
        return typeof value === 'number' &&
            isFinite(value) &&
            Math.floor(value) === value;
    };

    // Production steps of ECMA-262, Edition 6, 22.1.2.1
    if (!Array.from) {
        Array.from = (function() {
            var toStr = Object.prototype.toString;
            var isCallable = function(fn) {
                return typeof fn === 'function' || toStr.call(fn) === '[object Function]';
            };
            var toInteger = function(value) {
                var number = Number(value);
                if (isNaN(number)) { return 0; }
                if (number === 0 || !isFinite(number)) { return number; }
                return (number > 0 ? 1 : -1) * Math.floor(Math.abs(number));
            };
            var maxSafeInteger = Math.pow(2, 53) - 1;
            var toLength = function(value) {
                var len = toInteger(value);
                return Math.min(Math.max(len, 0), maxSafeInteger);
            };

            // The length property of the from method is 1.
            return function from(arrayLike /*, mapFn, thisArg */ ) {
                // 1. Let C be the this value.
                var C = this;

                // 2. Let items be ToObject(arrayLike).
                var items = arrayLike;

                // 3. ReturnIfAbrupt(items).
                if (arrayLike == null) {
                    throw new TypeError('Array.from requires an array-like object - not null or undefined');
                }

                // 4. If mapfn is undefined, then let mapping be false.
                var mapFn = arguments.length > 1 ? arguments[1] : void undefined;
                var T;
                if (typeof mapFn !== 'undefined') {
                    // 5. else
                    // 5. a If IsCallable(mapfn) is false, throw a TypeError exception.
                    if (!isCallable(mapFn)) {
                        throw new TypeError('Array.from: when provided, the second argument must be a function');
                    }

                    // 5. b. If thisArg was supplied, let T be thisArg; else let T be undefined.
                    if (arguments.length > 2) {
                        T = arguments[2];
                    }
                }

                // 10. Let lenValue be Get(items, "length").
                // 11. Let len be ToLength(lenValue).
                var len = toLength(items.length);

                // 13. If IsConstructor(C) is true, then
                // 13. a. Let A be the result of calling the [[Construct]] internal method 
                // of C with an argument list containing the single item len.
                // 14. a. Else, Let A be ArrayCreate(len).
                var A = isCallable(C) ? new C(len) : new Array(len);

                // 16. Let k be 0.
                var k = 0;
                // 17. Repeat, while k < len… (also steps a - h)
                var kValue;
                while (k < len) {
                    kValue = items[k];
                    if (mapFn) {
                        A[k] = typeof T === 'undefined' ? mapFn(kValue, k) : mapFn.call(T, kValue, k);
                    } else {
                        A[k] = kValue;
                    }
                    k += 1;
                }
                // 18. Let putStatus be Put(A, "length", len, true).
                A.length = len;
                // 20. Return A.
                return A;
            };
        }());
    }
    if (!String.prototype.substr) {
        String.prototype.substr = function(a, b) {
            var s = (!Number.isInteger(a)) ? 0 : a,
                l = (typeof b == 'undefined') ? null : (s > 0 && b > 0) ? s + b : b;
            if (s < 0) {
                s = this.length + a;
                l = (l < 0) ? 0 : s + l;
            }
            return (typeof b == 'undefined' && b != 0 && Number.isInteger(a)) ? this.substring(s) : (l <= 0 || !Number.isInteger(l)) ? "" : this.substring(s, l);
        };
    }

    /**
     * String.repeat()
     * version 0.0.0
     */
    if (!String.prototype.repeat) {
        Object.defineProperty(String.prototype, 'repeat', {
            configurable: true,
            writable: true,
            value: function(count) {
                if (this == null) {
                    throw new TypeError("can't convert " + this + ' to object');
                }
                var str = '' + this;
                count = +count;
                if (count != count) {
                    count = 0;
                }
                if (count < 0) {
                    throw new RangeError('repeat count must be non-negative');
                }
                if (count == Infinity) {
                    throw new RangeError('repeat count must be less than infinity');
                }
                count = Math.floor(count);
                if (str.length == 0 || count == 0) {
                    return '';
                }
                if (str.length * count >= 1 << 28) {
                    throw new RangeError('repeat count must not overflow maximum string size');
                }
                var rpt = '';
                for (;;) {
                    if ((count & 1) == 1) {
                        rpt += str;
                    }
                    count >>>= 1;
                    if (count == 0) {
                        break;
                    }
                    str += str;
                }
                return rpt;
            }
        });
    }

    /**
     * String.padStart()
     * version 1.0.1
     */
    if (!String.prototype.padStart) {
        Object.defineProperty(String.prototype, 'padStart', {
            configurable: true,
            writable: true,
            value: function(targetLength, padString) {
                targetLength = targetLength >> 0; //floor if number or convert non-number to 0;
                padString = (typeof padString !== 'undefined') ? padString : ' ';
                if (this.length > targetLength) {
                    return String(this);
                } else {
                    targetLength = targetLength - this.length;
                    if (targetLength > padString.length) {
                        padString += padString.repeat(targetLength / padString.length); //append to original to ensure we are longer than needed
                    }
                    return padString.slice(0, targetLength) + String(this);
                }
            }
        });
    }

    /**
     * String.padEnd()
     * version 1.0.1
     */
    if (!String.prototype.padEnd) {
        Object.defineProperty(String.prototype, 'padEnd', {
            configurable: true,
            writable: true,
            value: function(targetLength, padString) {
                targetLength = targetLength >> 0; //floor if number or convert non-number to 0;
                padString = (typeof padString !== 'undefined') ? padString : ' ';
                if (this.length > targetLength) {
                    return String(this);
                } else {
                    targetLength = targetLength - this.length;
                    if (targetLength > padString.length) {
                        padString += padString.repeat(targetLength / padString.length); //append to original to ensure we are longer than needed
                    }
                    return String(this) + padString.slice(0, targetLength);
                }
            }
        });
    }




    ///////////////////////////////////////////////////////////////////////
    //////////////////////////////           ////////////////////////////// 
    //////////////////////////////    END    ////////////////////////////// 
    //////////////////////////////           ////////////////////////////// 
    ///////////////////////////////////////////////////////////////////////




    try {


        var a = [
            { a: 5, b: 164, r: 80 },
            { a: 151, b: 31, r: -2147483648 },
            { a: -143, b: 223, r: -2147483648 },
            { a: -190, b: 430, r: -3112960 },
            { a: -474, b: 472, r: 637534208 },
            { a: 1073741824, b: 1, r: -2147483648 },
            { a: 1073741824, b: 2, r: 0 },
            { a: 5, b: 3, r: 40 },
            { a: -1, b: 1, r: -2 }

        ];


        for (var i = 0; i < a.length; i++) {
            v = a[i]
            var rr = util.leftShift(v.a, v.b);
            Write(v.a + ' << ' + v.b + ' == ' + v.r + '(' + rr + ') | ' + (rr == v.r)+'<br/>');
        }

    } catch (e) {
        Write(Stringify(e))
    }
</script>

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.