检查两个无符号整数之间的差是否最大为1 [英] Check if the difference between two unsigned integers is at most 1
问题描述
我正在寻找一种快速的方法来检查两个无符号整数之间的差是否最大为1.
I'm looking for a quick way to check whether or not the difference between two unsigned integers is at most 1.
很明显,我可以直接通过x <= y + 1 && y <= x + 1
来做到这一点.
Obviously, I can do it directly via x <= y + 1 && y <= x + 1
.
另一种方法是通过x == (x + y) / 2 || y == (x + y) / 2
.
但是我认为必须要有一个巧妙的技巧才能实现这一目标.
But I've figured there must be a bit-wise trick to achieve that.
所以我很高兴听到建议.
So I would be happy to hear suggestions.
您可以假定这两种输入类型相同,并且在添加它们时没有溢出.
You may assume that the two input types are identical, and that there is no overflow in adding them.
推荐答案
由于环绕式工程有效,因此x - y + 1 <= 2
怎么样.而且由于-n - 1
是一个补码,即~
,并且Solidity整数像C无符号整数一样具有环绕效果,因此您还可以使用-~x - y <= 2
,它的常数要少一个.
Since wraparound works, how about just x - y + 1 <= 2
. And since -n - 1
is one's complement, i.e ~
, and Solidity integers have wraparound just like C unsigned integers, then you could also use -~x - y <= 2
which has one constant less.
#include <stdio.h>
void test(unsigned int a, unsigned int b) {
printf("%d and %d: ", a, b);
printf("method1 %d ", a - b + 1 <= 2);
printf("method2 %d\n", -~a - b <= 2);
}
int main(void) {
test(1, 1);
test(1, 2);
test(1, 3);
test(1, 4);
test(2, 1);
test(3, 1);
test(4, 1);
}
输出:
1 and 1: method1 1 method2 1
1 and 2: method1 1 method2 1
1 and 3: method1 0 method2 0
1 and 4: method1 0 method2 0
2 and 1: method1 1 method2 1
3 and 1: method1 0 method2 0
4 and 1: method1 0 method2 0
在Solidity中,旋转一下并不能真正帮到您-您需要查看汽油费用表用于不同的操作.第一个执行3个非常低的算术运算和两次下推,第二个执行4个非常低的算术运算和一次下推,因此它们应该或多或少具有可比性.
In Solidity, bit twiddling does not really help you that much - you need to look into the gas cost table for different operations. The first does 3 verylow arithmetic operations and two pushes, the second one does 4 verylow arithmetic operations and one push, so they should be more or less comparable.
这篇关于检查两个无符号整数之间的差是否最大为1的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!