如何计算二进制数的最大C块长度

Question

我想重申的事实是，我并不是要求直接针对我的问题编写代码，而是想要关于如何实现该解决方案的信息。

我之前问了一个关于在二进制代码中计算特定整数的问题。现在我想问一下如何计算二进制码中的最大块长度。

老实说，我只是想知道从哪里开始，通过编写代码来计算输入的整数二进制表示的“最大块长度”，以及问题的确切含义。

例如:输入456输出: 111001000 1的数量:4最大块长度：？

这是我到目前为止的代码，如果你想知道我是从哪里来的，可以参考。

#include <stdio.h>

int main(void)
{
  int integer; // number to be entered by user
  int i, b, n;
  unsigned int ones;
  printf("Please type in a decimal integer\n"); // prompt
  fflush(stdout);
  scanf("%d", &integer); // read an integer

  if(integer < 0)
  {
    printf("Input value is negative!"); // if integer is less than
    fflush(stdout);

    return;                  // zero, print statement
  }
  else{
    printf("Binary Representation:\n", integer);
    fflush(stdout);} //if integer is greater than zero, print statement

    for(i = 31; i >= 0; --i) //code to convert inputted integer to binary form
    {
      b = integer >> i;
      if(b&1){
        printf("1");
        fflush(stdout);
      }
      else{
        printf("0");
        fflush(stdout);
      }
    }
  printf("\n");
  fflush(stdout);
  ones = 0; //empty value to store how many 1's are in binary code
  while(integer)  //while loop to count number of 1's within binary code
  {
    ++ones;
    integer &= integer - 1;
  }
  printf("Number of 1's in Binary Representation: %d\n", ones); // prints number
  fflush(stdout);                                           //of ones in binary code
  printf("Maximum Block Length: \n");
  fflush(stdout);
  printf("\n");
  fflush(stdout);
  return 0;

}//end function main

Answer 1

假设你正在寻找1的最长运行时间。

这是如何在32位上做到这一点的。你应该能够将这个想法扩展到任意长度的比特流。

int maxRunLen(uint32_t num) {
    int count = 0; 
    int maxCount = 0;
    while(num) {
       if(num & 1) count++;
       else {
           if( count > maxCount) maxCount = count;
           count = 0;
       }
       num >>=1;
    }
    if( count > maxCount) maxCount = count;
    return maxCount;
}

这个想法是测试每个比特，以确定它是否是1。如果为1，则递增计数。否则，它将结束一次运行，在这种情况下，检查前一次运行是否比前一次最大运行时间长，并重置计数。

测试bit的方法是使用掩码。在上面的示例中，测试的最低阶位

num & 1

要测试数字中的下一位，需要将所有位向右移动1位，这称为移位。更明确地说，在这种情况下，逻辑右移(>>)。示例位模式0110变为0011。这是在上面的示例中完成的：

num >>= 1;

相当于：

num = num >> 1;

Answer 2

试试这个：

int max_run_of_ones (unsigned x)
{
  int max_run = 0;
  int cur_run;

  while (x != 0) {
    // skip right-most zeros                                                    
    while ((x & 1) == 0) {
      x >>= 1;
    }
    // skip and measure right-most run of ones                                  
    cur_run = 0;
    while ((x & 1) == 1) {
      cur_run++;
      x >>= 1;
    }
    if (cur_run > max_run) max_run = cur_run;
  }
  return max_run;
}

Answer 3

这应该可以在python中解决这个问题，使用字符串操作...

这样做的主要目的是帮助其他人理解你想要实现的目标。

import re    

number = 500
binary_repr = bin(number)[2:]             # '111110100'
blocks = re.split(r'0+', binary_repr)     # ['11111', '1', '']
block_lengths = [len(x) for x in blocks]  # [5, 1, 0]
maximum_block_length = max(block_lengths) # 5