0

我想重申一个事实,即我不是要求直接为我的问题提供代码,而是想要有关如何达到该解决方案的信息。

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

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

例如:输入 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
4

4 回答 4

3

假设您正在寻找最长的 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,则增加计数。否则,它是运行的结束,在这种情况下,检查前一次运行是否比任何前一次最大运行时间长并重置计数。

测试一点的方法是使用掩码。在上面的例子中,最低位的测试由

num & 1

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

num >>= 1;

这相当于:

num = num >> 1;
于 2012-09-12T03:06:11.920 回答
1

尝试这个:

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;
}
于 2012-09-12T03:33:48.480 回答
0

通过查看您的代码,您似乎想知道设置的位数。这是一个猜测...

这要归功于 Ratko Tomic。这家伙在位操作方面非常出色。

int countBits(整数值)
{
    诠释 n = 0;

    如果(值)
    {
        做
        {
            n++;
        } while( 0 != (value = value & (value - 1) ) );
    }
    返回(n);
}
于 2012-09-12T02:55:37.307 回答
0

这应该在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
于 2012-09-12T03:05:05.727 回答