thzinc

binaryPal - Interview question of the week from rendezvous with cassidoo

What’s faster: a typical JavaScript implementation of .toString() and some basic string manipulation or clever bit shifting? (TL;DR: It’s bit shifting, but it’s uglier code.)

Interview question of the week

This week’s question: Write a function to find out whether the binary representation of a number is palindrome or not.

Example:

> binaryPal(5)
> true

> binaryPal(10)
> false

My solution

Written as a stream of consciousness

I’ll try to solve this as a string problem first. I know I can use the .toString(number) method to pretty efficiently translate a number into a base-2 string representation.

#mocha

  

function binaryPal(num) {
  const str = num.toString(2);
  for (let s = 0, e = str.length - 1; s < e; s++, e--) {
    if (str[s] !== str[e]) return false;
  }
  return true;
}

mocha.setup("bdd");
const assert = chai.assert;
const expect = chai.expect;
const should = chai.should();

describe("Given the examples from the question", () => {
  const expectations = [
    { input: 5, output: true },
    { input: 10, output: false },
  ];
  expectations.forEach(({ input, output }) => {
    it(`should return ${output} for the input ${input}`, () => {
      binaryPal(input).should.equal(output);
    });
  });
});

describe("Given additional examples", () => {
  const expectations = [
    { input: -1, output: false },
    { input: 0, output: true },
    { input: 1, output: true },
    { input: 2, output: false },
    { input: 1234, output: false },
    { input: 0b1111, output: true },
    { input: 0b10000, output: false },
    { input: 0b1111111111, output: true },
    { input: 0b10000000000, output: false },
    { input: 0b110011, output: true },
    { input: 0b11011, output: true },
  ];
  expectations.forEach(({ input, output }) => {
    it(`should return ${output} for the input ${input}`, () => {
      binaryPal(input).should.equal(output);
    });
  });
});

mocha.run();

The string solution feels reasonably easy to read, and there’s nothing that stands out as particularly inefficient, except that each bit of memory used for num was multiplied by 8 to represent the number as a string of utf-8 characters.

ED: I was thinking along the following lines, but then got hung up on how to mathematically reverse the digits in a number without iterating for at least half the number of digits.

After plinking around in the programmer calculator mode, I think there’s a way to accomplish this without iterating over the digits.

First problem to solve: calculate the number of significant digits in the number. A quick search turned up Number of Bits in a Decimal Integer, which boils down to Math.ceil((Math.log(num)/Math.log(2)))

Second problem to solve: how to reverse a sequence of bits.

So, if I’m still going to iterate over digits, what does that look like with bit shifting?

#mocha

  

function binaryPal(num) {
  if (num < 0) return false; // Reject negative numbers
  if (num < 2) return true; // Zero and one are both palindromic

  let acc = num & 0b1;
  if (acc === 0) return false; // Even numbers cannot be base-2 palindromes

  let dec = num >> 1;

  while (acc <= dec) {
    if (dec === acc) return true;

    const n = dec & 0b1;
    dec >>= 1;
    if (dec === acc) return true;

    acc = (acc << 1) | n;
  }
  return false;
}

mocha.setup("bdd");
const assert = chai.assert;
const expect = chai.expect;
const should = chai.should();

describe("Given the examples from the question", () => {
  const expectations = [
    { input: 5, output: true },
    { input: 10, output: false },
  ];
  expectations.forEach(({ input, output }) => {
    it(`should return ${output} for the input ${input}`, () => {
      binaryPal(input).should.equal(output);
    });
  });
});

describe("Given additional examples", () => {
  const expectations = [
    { input: -1, output: false },
    { input: 0, output: true },
    { input: 1, output: true },
    { input: 2, output: false },
    { input: 1234, output: false },
    { input: 0b1111, output: true },
    { input: 0b10000, output: false },
    { input: 0b1111111111, output: true },
    { input: 0b10000000000, output: false },
    { input: 0b110011, output: true },
    { input: 0b11011, output: true },
  ];
  expectations.forEach(({ input, output }) => {
    it(`should return ${output} for the input ${input}`, () => {
      binaryPal(input).should.equal(output);
    });
  });
});

mocha.run();

After explicitly handling negative numbers and zero and one, I’m taking the approach of shifting one off of dec and building up acc from left to right, then seeing if they’re equal OR if they’re equal after shifting one more bit off of dec. (This handles odd numbers of digits because the digit in the middle of a palindrome doesn’t change the outcome of the result.)

So, is one of these faster than the other?


#mocha
#results

  

mocha.setup("bdd");
const assert = chai.assert;
const expect = chai.expect;
const should = chai.should();

describe("When comparing a string-based implementation to a bit shift-based implementation", () => {
  const maxIterations = 1_000_000;
  const stringImpl = getStringImpl();
  const bitShiftImpl = getBitShiftImpl();

  const results = [];
  for (const subject of [stringImpl, bitShiftImpl]) {
    const start = performance.now();
    for (let i = 0; i < maxIterations; i++) {
      const rand = Math.round(Math.random() * 1_000_000_000_000);
      subject(rand);
    }
    const end = performance.now();
    results.push(end - start);
  }
  const [stringElapsedTimeMs, bitShiftElapsedTimeMs] = results;

  (function () {
    document.getElementById("results").innerHTML = `
      <ul>
        <li>string-based implementation: ${stringElapsedTimeMs} ms over ${maxIterations} invocations</li>
        <li>bit shift-based implementation: ${bitShiftElapsedTimeMs} ms over ${maxIterations} invocations</li>
      </ul>
    `;
  })();

  it("bit shifting should be faster", () => {
    bitShiftElapsedTimeMs.should.be.below(stringElapsedTimeMs);
  });
});

mocha.run();


// Glue...
function getStringImpl(){
function binaryPal(num) {
  const str = num.toString(2);
  for (let s = 0, e = str.length - 1; s < e; s++, e--) {
    if (str[s] !== str[e]) return false;
  }
  return true;
}

return binaryPal;}
function getBitShiftImpl(){
function binaryPal(num) {
  if (num < 0) return false; // Reject negative numbers
  if (num < 2) return true; // Zero and one are both palindromic

  let acc = num & 0b1;
  if (acc === 0) return false; // Even numbers cannot be base-2 palindromes

  let dec = num >> 1;

  while (acc <= dec) {
    if (dec === acc) return true;

    const n = dec & 0b1;
    dec >>= 1;
    if (dec === acc) return true;

    acc = (acc << 1) | n;
  }
  return false;
}

return binaryPal;}

Seems like bit shifting is faster by 7-8 times running in a browser on my computer. Sample output:

  • string-based implementation: 799 ms over 1000000 invocations
  • bit shift-based implementation: 109 ms over 1000000 invocations

My bit shifting implementation is definitely not as readable or as easy to translate back to the original prompt, but that’s usually the tradeoff when optimizing code.

Update

A colleague of mine pointed out that the JavaScript engine’s just-in-time compilation cache may be artificially inflating the execution time of the first test. To keep things simple, when I repeat the test four times, I get slightly improved results on the string-based implementation, so now it’s only about 6 times slower than bit shifting instead of 7-8 times slower.

Thanks Bondor!


#mocha
#results

  

mocha.setup("bdd");
const assert = chai.assert;
const expect = chai.expect;
const should = chai.should();

describe("When comparing a string-based implementation to a bit shift-based implementation", () => {
  const maxIterations = 1_000_000;
  const stringImpl = getStringImpl();
  const bitShiftImpl = getBitShiftImpl();

  const results = [];
  for (const subject of [
    stringImpl,
    bitShiftImpl,
    stringImpl,
    bitShiftImpl,
    stringImpl,
    bitShiftImpl,
    stringImpl,
    bitShiftImpl,
  ]) {
    const start = performance.now();
    for (let i = 0; i < maxIterations; i++) {
      const rand = Math.round(Math.random() * 1_000_000_000_000);
      subject(rand);
    }
    const end = performance.now();
    results.push(end - start);
  }
  const [stringElapsedTimeMs, bitShiftElapsedTimeMs] = results.slice(-2);

  (function () {
    document.getElementById("results").innerHTML = `
      <ul>
        ${results
          .map((elapsedMs, i) => {
            const impl = i % 2 == 0 ? "string-based" : "bit shift-based";
            return `<li>${impl} implementation: ${elapsedMs} ms over ${maxIterations} invocations</li>`;
          })
          .join("")}
      </ul>
    `;
  })();

  it("bit shifting should be faster", () => {
    bitShiftElapsedTimeMs.should.be.below(stringElapsedTimeMs);
  });
});

mocha.run();


// Glue...
function getStringImpl(){
function binaryPal(num) {
  const str = num.toString(2);
  for (let s = 0, e = str.length - 1; s < e; s++, e--) {
    if (str[s] !== str[e]) return false;
  }
  return true;
}

return binaryPal;}
function getBitShiftImpl(){
function binaryPal(num) {
  if (num < 0) return false; // Reject negative numbers
  if (num < 2) return true; // Zero and one are both palindromic

  let acc = num & 0b1;
  if (acc === 0) return false; // Even numbers cannot be base-2 palindromes

  let dec = num >> 1;

  while (acc <= dec) {
    if (dec === acc) return true;

    const n = dec & 0b1;
    dec >>= 1;
    if (dec === acc) return true;

    acc = (acc << 1) | n;
  }
  return false;
}

return binaryPal;}

See also