比特＃需要重新present一个数字x [英] # of bits needed to represent a number x

问题描述

我目前正在写，确定多少位需要重新present一个数字x的算法。我的实施将在C。
有几个渔获不过，我仅限于pretty简单，只是按位运算符{〜，＆安培;，^，|，+，LT;＆LT ;, >>}。另外，我不能使用任何类型的控制流（如，同时，为）。
我原来的办法是检查二进制数由左到右，并查找那里是第一'1'的发生。我不知道如何处理这个给我的限制。
我与工作数量可以被认为是一个无符号整数。所以00110将只需要3个位。

我想知道是否有一个更容易/清洁的方式做到这一点，我失踪了吗？
或者，如果有人可以给一些提示？

基本上，我是想实现这个不while循环：

  INT结果= 0;
  而（X GT;＆GT; = 1）{
    结果+ = 1;
  }
  返回结果;
 

解决方案

HTTP ：//www-graphics.stanford.edu/~seander/bithacks.html#IntegerLog

示范如何做没有控制流。

 无符号整型伏; // 32位值来查找的LOG2
注册无符号整数读; // LOG2的结果（v）将去这里
注册unsigned int类型转变;R =（V＆GT; 0xFFFF的）LT;＆LT; 4; V＆GT;＆GT; = R;
移=（V＆GT; 0xFF的）LT;＆LT; 3; V＆GT;＆GT; =移位; -  [R | =转变;
移=（V＆GT; 0xF的）LT;＆LT; 2; V＆GT;＆GT; =移位; -  [R | =转变;
移=（V＆GT; 0x3中）LT;＆LT; 1; V＆GT;＆GT; =移位; -  [R | =转变;
                                        ř| =（V＆GT;大于1）;
 -  [R ++;
 

I am currently trying to write an algorithm that determines how many bits are necessary to represent a number x. My implementation will be in c. There are a few catches though, I am restricted to pretty much just the bitwise operators {~, &, ^, |, +, <<, >>}. Also, I cannot use any type of control flow (if, while, for). My original approach was to examine the number in binary from left to right, and look for where there is an occurrence of the first '1'. I am not sure how to approach this given the restrictions I have. The number I am working with can be considered an unsigned integer. So 00110 would require only 3 bits.

I am wondering if there is a much easier/cleaner way to do this and I am missing it? Or if someone can give a few hints?

Basically, I was trying to implement this without the while loop:

 int result = 0;
  while (x >>= 1) {
    result += 1;
  }
  return result;

解决方案

http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLog

Shows how to do it without control flow.

unsigned int v;          // 32-bit value to find the log2 of 
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;

r =     (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF  ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF   ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3   ) << 1; v >>= shift; r |= shift;
                                        r |= (v >> 1);
r++;

这篇关于比特＃需要重新present一个数字x的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！