按位操作帮助/建议 [英] Bitwise Operations Help/Suggestions

问题描述

好的，我不是在寻找答案或类似的东西.因此，在最近的考试中，当我被要求执行一些相对简单的按位运算时，我似乎无法完成工作.给定30分钟到一个小时的时间，我可以将其冲洗掉，但是用10分钟或更短的时间，我就会被卡住.

Alright, I'm not looking for answers or anything like that. So on recent exams, when I've been asked to perform some relatively simple bitwise operations, I just can't seem to get the job done. Given 30 minutes to an hour, I could flush it out, but with 10 minutes or less, I just get stuck.

例如，最近我被要求编写一个小函数，如果x> y，则返回1，否则返回0. 我无法为我的生活提供答案.考试结束后，我回家写了答案，但花了我半个小时.

For example, i was recently asked to write a small function, if x > y,return 1, else 0. I couldnt for the life of me provide an answer. After the exam, I went home and wrote out the answer, but it took me half an hour.

我正在竭尽全力来加快速度，因为我知道我将在决赛中再次遇到此类问题.

Im doing my best to get faster at this because I know I'm going to get these kind of questions again on the final.

一些规则，公理或我可以用来帮助我解决此类问题的任何东西.当您看到这样的问题时，什么推理可以帮助您形成答案.

What are some rules, axioms, or anything that I can utilize to help me get going on these kind of problems. When you see a problem like this, what reasoning helps you form an answer.

推荐答案

您将需要以下常识

• 对C运算符的了解
• 2的补数算法
• 布尔代数

可能有用的一个技巧是 n位折叠.例如，假设我给我一个32位值作为函数的参数，并且如果任何一位为1，则我需要返回1，否则为0. (进一步假设问题的规则不允许我以任何明智的方式进行此操作.)然后我的函数将如下所示:

A trick that may come in handy is n-bit folding. For example, let's say I'm given a 32-bit value as the argument to my function, and I need to return 1 if any of the bits is 1, or 0 otherwise. (Further assume that the rules of the question don't allow me to do this in any sensible fashion.) Then my function would look like this

int hasBitsSet(uint32_t value)
{
    value |= value >> 16;
    value |= value >>  8;
    value |= value >>  4;
    value |= value >>  2;
    value |= value >>  1;

    return value & 1;
}

函数的前五行折叠" 32位值，因此，如果任何一位为1，则结果的LSB将为1.函数的最后一行返回LSB.使用蛮力布尔代数，等效函数为

The first five lines of the function "fold" the 32-bit value, so that if any bit is a 1, then the LSB of the result will be a 1. The last line of the function returns the LSB. Using brute force boolean algebra, the equivalent function is

int hasBitsSet(uint32_t value)
{
    uint32_t bit31 = (value >> 31) & 1;
    uint32_t bit30 = (value >> 30) & 1;
    ...
    uint32_t bit0  = value & 1;

    return bit31 | bit30 | ... | bit0;
}

重点是 folding 有时在减少您必须编写的代码量方面很有用，但是您可以使用 folding 进行的任何操作都可以完成.蛮力布尔布尔代数.因此，如果不确定 folding 是否行得通，那就做代数.

The point is that folding is sometimes useful in reducing the amount of code that you have to write, but anything that you can do with folding can also be done with brute-force boolean algebra. So if you're not sure whether folding will work, then just do algebra.

我要说的最后一件事是，比较通常是通过减法来实现的.换句话说，要确定是否为x > y，请首先计算x - y，然后检查结果是否为正.在2的补码算法中，如果MSB为0，且其他位中的至少一位为1，则数字为正.因此，您可以提取MSB，将其他31位进行折叠，然后使用布尔代数生成最终结果.

The final thing I'll mention is that comparisons are often implemented by subtraction. In other words, to determine whether x > y, first compute x - y, and then check whether the result is positive. In 2's complement arithmetic, a number is positive if the MSB is 0 and at least one of the other bits is a 1. So you could extract the MSB, fold the other 31 bits, and then use boolean algebra to generate the final result.

最后一点知识(等同于减法)是特定于问题的，并且特别麻烦，因为每个问题都有一些奥秘的知识点，使问题变得更容易.您所能做的就是在课堂上集中注意力，并希望这些小宝石在被提及时会牢记在您的脑海中.

That last bit of knowledge (comparison equivalence to subtraction) is problem-specific and is especially troublesome since every question will have some arcane tidbit of knowledge that makes the question easier. All you can do about that is pay attention in class and hope that those little gems stick in your mind when they're mentioned.

这篇关于按位操作帮助/建议的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！