C-带按位运算符的饱和有符号整数乘法 [英] C - Saturating Signed Integer Multiplication with Bitwise Operators

问题描述

好的，所以我要做的赋值是将一个有符号整数乘以2并返回该值.如果该值溢出，则通过返回Tmin或Tmax使其饱和.挑战在于仅使用这些逻辑运算符(！〜& ^ | +<< >>)，而没有(if语句，循环等)，并且最多只能使用20个逻辑运算符.

Alright, so the assignment I have to do is to multiply a signed integer by 2 and return the value. If the value overflows then saturate it by returning Tmin or Tmax instead. The challenge is using only these logical operators (! ~ & ^ | + << >>) with no (if statements, loops, etc.) and only allowed a maximum of 20 logical operators.

现在我想解决这个问题的过程首先是找到极限.因此，我将Tmin/max除以2得到边界.这就是我所拥有的:

Now my thought process to tackle this problem was first to find the limits. So I divided Tmin/max by 2 to get the boundaries. Here's what I have:

正面

此及更高版本的作品:

1100000...

这个和更低的不是:

1011111...

如果它不起作用，我需要退货:

If it doesn't work I need to return this:

100000...

否定

此及下层作品:

0011111...

这个及更高版本没有:

0100000...

如果它不起作用，我需要退货:

If it doesn't work I need to return this:

011111...

否则，我必须返回:

2 * x;

(顺便说一下，整数是32位的)

(the integers are 32-bit by the way)

我看到前两位对于确定问题是否应返回2 * x或极限很重要.例如，XOR会执行此操作，因为如果前至后的位相同，则应返回2 * x，否则应返回限制.然后，对于整数的符号，还需要另一个if语句，因为它需要返回Tmin，否则必须返回Tmin.

I see that the first two bits are important in determining whether or not the problem should return 2*x or the limits. For example an XOR would do since if the first to bits are the same then 2*x should be returned otherwise the limits should be returned. Another if statement is then needed for the sign of the integer for it is negative Tmin needs to be returned, otherwise Tmax needs to be.

现在我的问题是，如何在不使用if语句的情况下做到这一点? xD还是更好的问题是我计划在受限的情况下工作或什至可行的方式?甚至更好的问题是是否有更简单的方法来解决此问题，如果可以，怎么办?任何帮助将不胜感激！

Now my question is, how do you do this without using if statements? xD Or a better question is the way I am planning this out going to work or even feasible under the constraints? Or even better question is whether there is an easier way to solve this, and if so how? Any help would be greatly appreciated!

推荐答案

a = (x>>31); // fills the integer with the sign bit 
b = (x<<1) >> 31; // fills the integer with the MSB 
x <<= 1; // multiplies by 2
x ^= (a^b)&(x^b^0x80000000); // saturate

那么这是如何工作的.前两行使用算术右移将所选位填充整个整数.

So how does this work. The first two lines use the arithmetic right shift to fill the whole integer with a selected bit.

最后一行基本上是"if语句".如果a==b，则右侧求值为0，并且x中的所有位均不翻转.否则，必须是 a==~b并且右侧求值为x^b^0x80000000的情况. 应用该语句后，x将等于x^x^b^0x80000000 => b^0x80000000，恰好​​是饱和度值.

The last line is basically the "if statement". If a==b then the right hand side evaluates to 0 and none of the bits in x are flipped. Otherwise it must be the case that a==~b and the right hand side evaluates to x^b^0x80000000. After the statement is applied x will equal x^x^b^0x80000000 => b^0x80000000 which is exactly the saturation value.

这是在实际程序的上下文中.

Here is it in the context of an actual program.

#include<stdio.h>
main(){
    int i = 0xFFFF;
    while(i<<=1){
        int a = i >> 31;
        int b = (i << 1) >> 31;
        int x = i << 1;
        x ^= (a^b) & (x ^ b ^ 0x80000000);
        printf("%d, %d\n", i, x);
    }
}

这篇关于C-带按位运算符的饱和有符号整数乘法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！