使用位运算三个整数最大？ [英] Maximum of three integers using bitwise operations?

问题描述

我将如何回报最大的，如只使用位运算三个无符号整数，〜，|，＆安培;！，^ +，>>，＆LT;＆LT ;.我不知道从哪里开始。任何帮助将是AP preciated。

编辑：

我只允许使用指定的法律OPS，完蛋了。

  / ** maxOfThree  - 返回最大的三个整数。
*注：X，Y，Z都在范围[0，TMAX。
*实施例：maxOfThree（1，2，3）= 3
*法律OPS！ 〜＆安培; ^ | + LT;＆LT; ＆GT;＆GT;
*最大OPS：25
INT maxOfThree（INT X，INT Y，INT Z）{
}
 

解决方案

看一看了的位摆弄黑客的页面和学习/如何最大最小的贯彻落实。

如果你能弄清楚如何为两个数字作品的最大值，那么你就可以概括的情况下三个数字。

让我给你解释一下这两个号码的情况下获取最大的价值：

---

- （A＆LT; B）可以返回-1或0，那么你可以有 11111111 11111111 11111111 11111111 （-1补为一个int）或 00000000 00000000 00000000 00000000 （-0 == 0为一个int）。

记住， A ^ B ^ B = A 和 A ^ B ^ A = B （没有按' ŧ重要的顺序是什么，这是 XOR操作），你有在第一种情况：

• 如果 A＆LT; b 你需要返回b的结果，所以

A ^（（A ^ B）及 - （A＆LT; B））必须等于 A ^ A ^ B ..事实上它是自 - （A＆LT; b）收益 11111111 11111111 11111111 11111111 ，和一个和按位＆放大器;在 11111111 11111111 11111111 11111111 一个无符号整数叶数不变......从而 A ^ A ^ B = 。这是最大

• 如果 A＆GT; b 然后 A＆LT; b 是假的，从而（任何与放大器; 00000000 00000000 00000000 00000000） 0。就这样，你有 A ^ 0 ，这是一个。最大的。

最后，我们有解决方案概括为三个数字：

 的#include＆LT;＆stdio.h中GT;INT GetMax的（unsigned int类型一，无符号整型B，无符号整型C）{
    INT TEMP = A ^（（A ^二）及;  - （A＆LT; B））;
    INT R = C ^（（C ^温度）及 - （℃下温））;
    返回ř;
}诠释主要（无效）{
    unsigned int类型A = 3，B = 1，C = 9;    的printf（％d个，GetMax的（A，B，C））;
    返回0;
}
 

---

编辑：如果你不能使用＆LT;然后使用第二个版本。

  X  - （（X  -  Y）及（（X  -  Y）＆​​GT;＆GT;（的sizeof（int）的* CHAR_BIT  -  1）））;
 

和牢记以下摘录

  

请注意，1989年的ANSI C标准没有规定的结果
  签署右移，所以这些是不可移植的。如果抛出异常
  上溢，则x和y的值应是无符号或投射到
  无符号的增减，避免不必要地抛​​出
  例外，然而右移需要一个符号操作数以产生
  当负都是一个位，所以转换为签订有

---

编辑II：这应该与您发布的规范工作：

 的#include＆LT;＆stdio.h中GT;INT GetMax的（INT X，INT Y，INT Z）{
    INT R =（X +〜（（X +〜Y + 1）及（（X +〜Y + 1）＆GT;＆GT; 31））+ 1）; //如果可能使用的sizeof（int）的*的sizeof（char）的31 +〜0代替
    INT R2 =（Z +〜（（Z +〜R + 1）及（（Z +〜R + 1）＆GT;＆GT; 31））+ 1）; //如果可能使用的sizeof（int）的*的sizeof（char）的31 +〜0代替
    返回R2;
}诠释主要（无效）{
    unsigned int类型1 = 5，B = 7，C = 1;    的printf（％d个，GetMax的（A，B，C））;
    返回0;
}
 

请注意，它会更好，如果你可以使用的sizeof（），而不是仅仅假设一个int是4字节（它不是在所有平台上如此）。

How would I return the maximum of three unsigned integers using only bit-wise operations, such as !,~,|,&,^,+,>>,<<. I don't know where to start. Any help would be appreciated.

edit:

I am only allowed to use the given legal ops, thats it.

/** maxOfThree - Returns the maximum of three integers.
* NOTE: x, y, z are all in the range [0, TMax].
* Examples: maxOfThree(1, 2, 3) = 3
* Legal Ops: ! ~ & ^ | + << >>
* Max Ops: 25
int maxOfThree(int x, int y, int z) {
}

解决方案

Take a look at the "bit-twiddling hacks" page and study how maximum/minimum are implemented.

If you can figure out how the maximum for two numbers works, then you can generalize the case for three numbers.

Let me explain to you the two-numbers case for getting the maximum value:

---

-(a<b) can either return -1 or 0, then you can have either 11111111 11111111 11111111 11111111 (-1 in two's complement for an int) or 00000000 00000000 00000000 00000000 (-0 == 0 for an int).

Remembering that a^b^b = a and that a^b^a = b (doesn't matter what the order is, this is the xor operation), you have that in the first case:

• If a < b you need to return b as result, so

a ^ ((a ^ b) & -(a < b)) must be equal to a ^ a ^ b.. and in fact it is since -(a<b) returns 11111111 11111111 11111111 11111111, and an and-bitwise & operated on 11111111 11111111 11111111 11111111 for an unsigned integer leaves the number unchanged... thus a ^ a ^ b = b. This is the maximum.

• If a > b then a < b is false, thus (anything & 00000000 00000000 00000000 00000000) is 0. And thus you have a ^ 0, which is, a. The maximum.

And finally we have the solution generalized for three numbers:

#include <stdio.h>

int getMax(unsigned int a, unsigned int b, unsigned int c) {
    int temp = a ^ ((a ^ b) & -(a < b)) ;
    int r = c ^ ((c ^ temp) & -(c < temp));
    return r;
}

int main(void) {
    unsigned int a = 3, b = 1, c = 9;

    printf("%d", getMax(a,b,c));
    return 0;
}

---

Edit: if you're not allowed to use "<" then use the second version

x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)));

and keep in mind the following excerpt

Note that the 1989 ANSI C specification doesn't specify the result of signed right-shift, so these aren't portable. If exceptions are thrown on overflows, then the values of x and y should be unsigned or cast to unsigned for the subtractions to avoid unnecessarily throwing an exception, however the right-shift needs a signed operand to produce all one bits when negative, so cast to signed there

---

Edit II: this should work with the specification you posted:

#include <stdio.h>

int getMax(int x, int y, int z) {
    int r  =  (x + ~((x+~y+1) & ((x+~y+1) >> 31))+1); // if possible use sizeof(int)*sizeof(char)+~0 instead of 31
    int r2 =  (z + ~((z+~r+1) & ((z+~r+1) >> 31))+1); // if possible use sizeof(int)*sizeof(char)+~0 instead of 31
    return  r2;
}

int main(void) {
    unsigned int a = 5, b = 7, c = 1;

    printf("%d", getMax(a,b,c));
    return 0;
}

Notice that it would be better if you could use sizeof() instead of just assuming that an int is 4 bytes (it isn't true on all platforms).

这篇关于使用位运算三个整数最大？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！