- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我有一个 byte
用于存储位标志。我需要计算字节中最高有效位的位置。
示例字节: 00
1
01101
=> 6
是最高位设置位的位置
紧凑的十六进制映射:
[0x00] => 0x00
[0x01] => 0x01
[0x02,0x03] => 0x02
[0x04,0x07] => 0x03
[0x08,0x0F] => 0x04
[0x10,0x1F] => 0x05
[0x20,0x3F] => 0x06
[0x40,0x7F] => 0x07
[0x80,0xFF] => 0x08
C 中的测试用例:
#include <stdio.h>
unsigned char check(unsigned char b) {
unsigned char c = 0x08;
unsigned char m = 0x80;
do {
if(m&b) { return c; }
else { c -= 0x01; }
} while(m>>=1);
return 0; //never reached
}
int main() {
unsigned char input[256] = {
0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f,
0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18,0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f,
0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28,0x29,0x2a,0x2b,0x2c,0x2d,0x2e,0x2f,
0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39,0x3a,0x3b,0x3c,0x3d,0x3e,0x3f,
0x40,0x41,0x42,0x43,0x44,0x45,0x46,0x47,0x48,0x49,0x4a,0x4b,0x4c,0x4d,0x4e,0x4f,
0x50,0x51,0x52,0x53,0x54,0x55,0x56,0x57,0x58,0x59,0x5a,0x5b,0x5c,0x5d,0x5e,0x5f,
0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0x6a,0x6b,0x6c,0x6d,0x6e,0x6f,
0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7a,0x7b,0x7c,0x7d,0x7e,0x7f,
0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,0x88,0x89,0x8a,0x8b,0x8c,0x8d,0x8e,0x8f,
0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,0x98,0x99,0x9a,0x9b,0x9c,0x9d,0x9e,0x9f,
0xa0,0xa1,0xa2,0xa3,0xa4,0xa5,0xa6,0xa7,0xa8,0xa9,0xaa,0xab,0xac,0xad,0xae,0xaf,
0xb0,0xb1,0xb2,0xb3,0xb4,0xb5,0xb6,0xb7,0xb8,0xb9,0xba,0xbb,0xbc,0xbd,0xbe,0xbf,
0xc0,0xc1,0xc2,0xc3,0xc4,0xc5,0xc6,0xc7,0xc8,0xc9,0xca,0xcb,0xcc,0xcd,0xce,0xcf,
0xd0,0xd1,0xd2,0xd3,0xd4,0xd5,0xd6,0xd7,0xd8,0xd9,0xda,0xdb,0xdc,0xdd,0xde,0xdf,
0xe0,0xe1,0xe2,0xe3,0xe4,0xe5,0xe6,0xe7,0xe8,0xe9,0xea,0xeb,0xec,0xed,0xee,0xef,
0xf0,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xf7,0xf8,0xf9,0xfa,0xfb,0xfc,0xfd,0xfe,0xff };
unsigned char truth[256] = {
0x00,0x01,0x02,0x02,0x03,0x03,0x03,0x03,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,
0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,
0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,
0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,
0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,
0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,
0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,
0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,
0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,
0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,
0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,
0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,
0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,
0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,
0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,
0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08};
int i,r;
int f = 0;
for(i=0; i<256; ++i) {
r=check(input[i]);
if(r !=(truth[i])) {
printf("failed %d : 0x%x : %d\n",i,0x000000FF & ((int)input[i]),r);
f += 1;
}
}
if(!f) { printf("passed all\n"); }
else { printf("failed %d\n",f); }
return 0;
}
我想简化我的 check()
函数,使其不涉及循环(最好是分支)。是否有一些小技巧或散列查找表解决方案来计算一个字节中最高有效位的位置?
最佳答案
您的问题是关于计算值的 log2
的有效方法。因为您似乎想要一个不限于 C 语言的解决方案,所以我有点懒惰并调整了一些我的 C# 代码。
您想计算 log2(x) + 1
并且对于 x = 0
(其中 log2
未定义)您将结果定义为0(例如,您创建了一个特殊情况,其中 log2(0) = -1
)。
static readonly Byte[] multiplyDeBruijnBitPosition = new Byte[] {
7, 2, 3, 4,
6, 1, 5, 0
};
public static Byte Log2Plus1(Byte value) {
if (value == 0)
return 0;
var roundedValue = value;
roundedValue |= (Byte) (roundedValue >> 1);
roundedValue |= (Byte) (roundedValue >> 2);
roundedValue |= (Byte) (roundedValue >> 4);
var log2 = multiplyDeBruijnBitPosition[((Byte) (roundedValue*0xE3)) >> 5];
return (Byte) (log2 + 1);
}
这个小技巧取自 Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup您可以在其中查看 32 位值的等效 C 源代码。此代码已经过调整以处理 8 位值。
但是,您可以使用一个非常有效的内置函数来使用一个操作来为您提供结果(在许多 CPU 上使用一条指令,如 Bit Scan Reverse)。问题的答案 Bit twiddling: which bit is set?有一些关于这个的信息。答案中的一句话提供了解决此问题的低级别支持的一个可能原因:
Things like this are the core of many O(1) algorithms such as kernel schedulers which need to find the first non-empty queue signified by an array of bits.
关于optimization - 确定字节中最高有效位的位置,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14511386/
我刚刚开始学习,我的一项练习需要帮助。 我需要最终用户输入每个月的降雨量。然后我需要输出平均降雨量、最高月份和最低月份以及降雨量高于平均水平的月份。 我一直在最高和最低中得到相同的数字,我不知道为什么
我试图让一排 div 都与最高的那个的高度相匹配,所以它们看起来是统一的。 我已经阅读了很多这方面的资料,但似乎找不到任何适用于跨浏览器的解决方案。 我目前使用的脚本是: var maxHei
我有一个像 [1,4,3,1,6,5,1,4,4] 的数组 这里最高元素频率是 3 ,我需要从数组中选择频率为 3 的所有元素,如上例中的 [1,4] 。 我已经尝试过这个 var count = {
我有一个学生记录列表,grades ,我想按 GPA 排序,返回前 5 个结果。由于某种原因count awk '{ if (count awk '{ if (count<=8) print $3,
我有一个用于显示博客文章的页面。在页面的开头,我使用以下 SQL 获取数据: SELECT posts.*, count(comments.post_id) as number_of_comments
我有一张 table 城市 |状态|比赛|值(value) 可以有多个相同城市/州/种族和不同值的记录。 我想创建一个新表,其中每个城市|州|种族有一条记录 与 计数(原始表中包含城市/州/种族的记录
我是一名初级 Java 程序员(例如 0 级...)。我正在做这个项目,但我已经被难住了好几天了。我可能还有很多我没有注意到的小错误。 项目是这样的: 要求用户输入从 0.00 到 100.00 的一
我已经对我的数据进行了分组。现在,我要做的是每周从“高”列中选择最高值,并从“低”列中选择最低值,然后使用最高值减去最低值得到范围。但是代码总是错误的。有人对我有想法吗? 这是我的 DataFrame
所以几个月前我在参加编程面试时,由于某种原因这个问题让我绊倒了。我可以想到几个解决方案,但其中大多数似乎效率极低。虽然多年来我一直以某种身份进行编程,但我目前正在大学攻读 CS 学位,所以我的引用点可
我已经制定了一个程序来显示给定日期的特定时间的最高和最低流行项目。该过程没有错误或异常,并且一切正常。如您所见,为了显示 Items 的第一条记录,查询重复了两次,但唯一的区别在于顺序(ASC 和 D
我正在尝试将配对的 div 设置为相同的高度。 Some text Some text Some textSome textSome textSome textSome text Som
R 提供了最大值和最小值,但除了对整个向量进行排序然后从此向量中选取值 x 之外,我没有看到一种真正快速的方法来查找顺序中的另一个值。 例如,是否有更快的方法来获取第二高值? 最佳答案 使用sort(
这是我的命令: top -b -n 1 | head -3 | tail -n 1 | awk '{ print $2 }' 我运行一个 bash 脚本来获取这些详细信息(还有平均负载和内存消耗)并将
对于这个计划,我的目标是...使用 findKth 查找最高分、最低分、中位数和平均分用户必须输入数字(输入-1以停止扫描),但他们不知道有多少个以及是否已排序但是,我在尝试执行此操作时遇到了一些问题
我正在创建这个网站: https://www.melkerhei.be/smeltkroes/index.html 左上角的标志应该是可以点击的。这是代码:
关闭。这个问题是off-topic .它目前不接受答案。 想改进这个问题吗? Update the question所以它是on-topic用于堆栈溢出。 关闭 9 年前。 Improve this
我的 table 是这样的: name | var ---------------- Joe | 3 Liz | 1 Liz | 4 Joe | 2 Peter
我有这个: function sayHello() { return new Promise( resolve => { throw new Error('reject');
JSFiddle:Example 我正在寻找一种方法来使容器 div 的高度等于其最高的子级。 每个其他子项的大小都应调整为容器的高度。 如果子元素超出其宽度,我还需要容器水平滚动。 到目前为止,我已
我有一个大小为 208 的列表(208 个句子数组),它看起来像: all_words = [["this is a sentence ... "] , [" another one hello bo
我是一名优秀的程序员,十分优秀!