计算二进制数中最大连续数1

Question

如何从二进制数中计算Java中最大连续数1？ 例如，用户输入一个像13这样的整数，这将在二进制1101中。 二进制数字1101有2个连续的1，所以输出应该是2. 另一个例子数字5是二进制0101，所以输出应该是1.我的程序无法正常工作，如果我输入数字439。

Scanner scanner = new Scanner(System.in); 
     int numb = scanner.nextInt(); 
     int tempCount = 0; 
     int count = 0; 

     // numb = 439 -> output 3 
     // numb = 13 -> output 2 
     // numb = 1 -> output 1 
     while (numb >= 1) { 

      if (numb % 2 != 0) { 

       tempCount++; 
       numb /= 2; 
       count = tempCount; 
       if (numb % 2 != 0) { 
        tempCount++; 
        count = tempCount; 
        numb /= 2; 
       } 

      } 
      else { 
       numb /= 2; 
       tempCount = 0; 
      } 
     } 
     System.out.println(count); 

Answer 1

我相信你打算count是l以1s的最长序列计算，而tempCount是当前计数序列中1的数量。因此，如果它大于count，则只应将tempCount指定为count。对于439，我相信你正确的计数三个1。然后出现0，并且您正确地将tempCount重置为零。下一次您计算1时，您正确地将tempCount增加为1，然后将此分配给count，并且您的三个计数会丢失。

Answer 2

我想通了，这里是解决方案。 我忘记了一个嵌套的if语句。

Scanner scanner = new Scanner(System.in); 
int numb = scanner.nextInt(); 
int tempCount = 0; //save temporarily the longest sequence of one's in this variable 
int count = 0; // before the sequence of one's gets interrupted, I save the value from tempCount in count 

// numb = 439 -> output 3 
// numb = 13 -> output 2 
// numb = 1 -> output 1 
while (numb >= 1) { 

    if (numb % 2 != 0) { 

     tempCount++; 
     numb /= 2; 
     if(count < tempCount){ 
      count = tempCount; 
     } 

    } 
    else { 
     numb /= 2; 
     tempCount = 0; 
    } 
} 
System.out.println(count); 

Answer 3

我们可以找出这样在至少显著位置上的两个连续的二进制的：

(value & 0b11) == 0b11 

我们可以在值移动的位到右侧，像这样：

value >>>= 1; 

这是重要的是使用tripple >>>超过双倍>>，因为我们不关心符号位。

那么我们需要做的就是保持连续1 S中的最大数量的轨道：

int countMax1Streak(int value) { // value could also be a long if required 
    int max = 0; 
    int count = 1; 
    while (value != 0) { 
     if ((value & 0b11) == 0b11) { 
      count++; 
     } else { 
      count = 1; 
     } 
     value >>>= 1; 
     if (count > max) { 
      max = count; 
     } 
    } 
    return max; 
} 

测试用例：

assertEquals(0, countMax1Streak(0b0)); 
assertEquals(1, countMax1Streak(0b1)); 
assertEquals(1, countMax1Streak(0b10)); 
assertEquals(2, countMax1Streak(0b11)); 
assertEquals(3, countMax1Streak(0b1110011)); 
assertEquals(3, countMax1Streak(0b1100111)); 
assertEquals(3, countMax1Streak(0b1110111)); 
assertEquals(7, countMax1Streak(0b1111111)); 
assertEquals(32, countMax1Streak(-1)); 

你也可以用它来计算最大0条纹状所以：

public int countMax0Streak(int value) { 
    return countMax1Streak(~value); 
} 

Answer 4

这是一个有趣的问题。这里是一个解决方案，它是通用的，也考虑所有long值可能在Java中（你的解决方案可能无法为负数，如果你检查的n值工作）：

public class LongestBitStreak { 

/** 
* Returns the longest <i>streak</i> of the given bit b in 
    given number n. 
* A bit streak is defined as a consecutive sequence of the given bit. 
* @param n the number to find streak in 
* @param b the bit whose streak is to be found 
* @return the <i>longest</i> bit streak 
*/ 
static int get(long n, int b) { 
    if (b != 0 && b != 1) 
     throw new IllegalArgumentException("second arg: (" + b + ") must be 0 or 1"); 
    int streak = 0, maxStreak = 0; 
    for (int i = 0; i < 64; i++) { 
     if ((n & 1) == b) { 
      streak += 1; 
      maxStreak = Math.max(streak, maxStreak); 
     } else { 
      streak = 0; 
     } 
     n >>= 1; 
    } 
    return maxStreak; 
} 

}

这里是一个有趣的单元测试：

@Test 
public void foolProof() { 
    long n = 0b11111000001111100110101010; 
    long nc = ~n; // One's complement of n 
    System.out.println(get(n, 1)); 
    System.out.println(get(nc, 0)); 
    assertEquals(get(n, 1), get(nc, 0)); 
    assertEquals(get(n, 0), get(nc, 1)); 
} 

注意一些优化基于数量和位的值是可能的，但是这应该是对于初学者一个体面的解决办法。