2
\$\begingroup\$

The task

Given an integer n, return the length of the longest consecutive run of 1s in its binary representation.

For example, given 156, you should return 3

My function solution 1

Style 1

function findMaxNumberOfConsecOnes(dec){
  const countConsecOnes = (acc, x) => [acc[0] < acc[1] 
                                       ? acc[1]
                                       : acc[0], 
                                       x === "1"
                                       ? acc[1] + 1
                                       : 0 ];

  return [...(dec >>> 0).toString(2)]
      .reduce(countConsecOnes, [0,0]);
}

Style 2

function findMaxNumberOfConsecOnes(dec){
  const countConsecOnes = (acc, x) => [acc[0] < acc[1] ? acc[1] : acc[0], 
                                       x === "1" ? acc[1] + 1 : 0 ];

  return [...(dec >>> 0).toString(2)]
      .reduce(countConsecOnes, [0,0]);

Style 1 and Style 2 have the exact same logic, but different style. My first idea was to write it in Style 1. But I then thought what was said to me in this thread about indentation. Therefore I opt for Style 2. But still not sure, whether this is the right way.

Alternatively:

My functional Solution 2

function findMaxNumberOfConsecOnes(dec){
  return [...(dec >>> 0).toString(2)]
    .reduce((acc, x) => {
      const current = x === "1" ? acc[1] + 1 : 0;
      const max = Math.max(acc[0], current);
      return [max, current];
  }, [0,0]);
}

My imperative Solution

function findMaxNumberOfConsecOnes(dec){
  const binStr = (dec >>> 0).toString(2);
  let max = 0, current = 0;
  for (const s of binStr) {
    current = s === "1" ? current + 1 : 0;
    max = Math.max(max, current);
  }
  return max;
}
\$\endgroup\$
  • \$\begingroup\$ There's nothing wrong with that style of indentation. Many formatters, such as Prettier and Perltidy, will apply it when using their default settings. Yes, you should be aware of line length but 100 characters is perfectly acceptable. \$\endgroup\$ – Oh My Goodness May 28 at 18:52
2
\$\begingroup\$

Code alignment.

I still think this style of indentation is poor. It is particularly ill suited to large code bases where you have literally hundreds of thousands of lines of code to maintain.

Its about reading the code and our inherently lazy brain. You scroll through the code looking for a problem scanning the lines and then you have code way to the right. Its not good.

I would write it as

function findMaxNumberOfConsecOnes(dec) {
    const countConsec = (ac, x) => [
        ac[0] < ac[1] ? ac[1] : ac[0], // or Math.max(...ac)
        x === "1" ? ac[1] + 1 : 0
    ];

    return [...(dec >>> 0).toString(2)]
        .reduce(countConsec, [0, 0])[0]; // Returning number rather than array
}

Note that I added () around the comma separated group and then the second ternary. Not because it is needed, but when you are checking code the IDE will highlight matching braces (I have mine set to bright bold red) saving time and effort when looking for typos in compound expressions..

Bug?

The functional solutions return differently (an array) from the imperative solution (a number). My guess is you forgot to extract the max from the array.

Number V String

Numbers always win.

I assume by the >>> 0 you are expecting negative values and that the MSB (most significant bit) the sign bit, is counted.

Strings are always the slowest way to deal with numbers. You do get an automatic reduction in the number of bits to count as toString(2) drops the leading zeros so it has one handy benefit.

Comparing your solutions

In terms of performance the imperative solution is the quickest at around 20% faster than the other two (tested on a random set of signed int32). This is almost a given as functional sacrifices performance in hope of less bugs.

Using numbers only

By avoiding the use of strings you avoid the memory allocation overhead and the slow string compare tests.

The following example is up to an order of magnitude faster than your imperative solution and can also avoid stepping over the leading bits of negative values.

  • size = Math.log2(Math.abs(num)) + 1 | 0 get the number of bits to count
  • const leading = num < 0 ? 32 - size : 0 If negative gets the number of leading bits
  • return Math.max(count + leading, max) add any leading bits to the count and check for max

The rest is straight forward.

function countBitSeq(num) {
    var max = 0, count = 0, size;
    size = Math.log2(Math.abs(num)) + 1 | 0;
    const leading = num < 0 ? 32 - size : 0;
    while (size --) {
        max = Math.max((num & 1 ? ++count : count = 0), max);
        num >>= 1;
    }
    return Math.max(count + leading, max);
}
\$\endgroup\$
  • \$\begingroup\$ Are the brackets set correctly? (In the rewritten code) \$\endgroup\$ – thadeuszlay May 29 at 5:40
  • \$\begingroup\$ @thadeuszlay Yes indeed, I had not yet run your code in my head, did not realize that you where returning the two items. Will fix it. \$\endgroup\$ – Blindman67 May 29 at 9:49
  • \$\begingroup\$ Even a master like you can make mistakes \$\endgroup\$ – thadeuszlay May 29 at 11:12

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.