2
\$\begingroup\$

The following code calculates the biggest number of consecutive ones in a binary representation of a number. For example 6 -> 2 (110), 5 -> 1 (101):

String numberAsBinaryString = Integer.toBinaryString(number);
List<String> listOfConsecutiveOneStrings = Arrays.asList(numberAsBinaryString.split("0"));

System.out.println(listOfConsecutiveOneStrings.stream()
                                                  .max(Comparator.comparing(String::length))
                                                  .map(onesSequence -> onesSequence.length())
                                                  .get());

I wonder if there is a more elegant way of writing this especially since this solution involves quite a few conversions. Any opinions are appreciated.

\$\endgroup\$
1
\$\begingroup\$

How about this? (maybe needs some adaption in Java):

int consBits(int x) {
    int consecutiveBits = 0;
    for(;x;consecutiveBits++)
        x &= (x<<1u);

    return consecutiveBits;
}

The idea is to binary & a number with a shifted version of itself. If it is not 0 there is a consecutive sequence of ones. Repeat until the result is 0 and we get the total length of consecutive ones.

\$\endgroup\$
  • \$\begingroup\$ That's a brilliant solution! \$\endgroup\$ – Joshua Dawson May 15 '16 at 21:14
0
\$\begingroup\$

The conversions aren't really necessary since you can just use bitshifts and masks to count the bits.

This should do it, although be wary of the sign bit. If your number can be negative and you want to ignore the sign bit, only loop up to 31:

int num = ?;
int count = 0;
int biggest = 0;
int mask = 0x0001;

for (int i = 0; i < 32; i++) {
  if (num & mask == mask) {
    count++;
  }
  else {
    if (count > biggest) {
      biggest = count;
    }
    count = 0;
  }
  num >>>= 1;
}

if (count > biggest) {
  biggest = count;
}

You might be able to speed this up by checking multiple bits at once.

\$\endgroup\$

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.