我正在尝试生成代码(目前使用clang ++ - 3.8),它添加了两个由多个机器字组成的数字.为了简化目前我只添加128位数字,但我希望能够概括这一点.
首先是一些typedef:
typedef unsigned long long unsigned_word;
typedef __uint128_t unsigned_128;
而"结果"类型:
struct Result
{
unsigned_word lo;
unsigned_word hi;
};
第一个函数f采用两对无符号字并返回结果,作为一个中间步骤,在添加它们之前将这两个64位字放入一个128位字中,如下所示:
Result f (unsigned_word lo1, unsigned_word hi1, unsigned_word lo2, unsigned_word hi2)
{
Result x;
unsigned_128 n1 = lo1 + (static_cast<unsigned_128>(hi1) << 64);
unsigned_128 n2 = lo2 + (static_cast<unsigned_128>(hi2) << 64);
unsigned_128 r1 = n1 + n2;
x.lo = r1 & ((static_cast<unsigned_128>(1) << 64) - 1);
x.hi = r1 >> 64;
return x;
}
这实际上非常好地内联:
movq 8(%rsp), …我和一个朋友来回与脑筋急转弯,我不知道如何解决这个问题.我的假设是,有些按位运算符是可能的,但不确定.
我有一段时间试图提出一个不违反C/C++标准的恒定时间旋转.
问题是边缘/角落情况,其中操作在算法中被调出并且那些算法不能被改变.例如,以下内容来自Crypto ++并执行GCC ubsan(即g++ fsanitize=undefined)下的测试工具:
$ ./cryptest.exe v | grep runtime
misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:643:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:625:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:643:22: runtime error: shift exponent 32 is …为什么在JVM内部类中存在的某些代码模式被转换为内部函数,而从我自己的类调用时相同的模式则不然.
例:
bitCount函数,当从Integer.bitCount(i)内调用时,将变成一个内在函数.但是当复制到我的类中然后调用将需要更长的时间来执行.
相比
Integer.bitCount(i)
MyClass.bitCount(i)
public static int bitCount(int i) {
// HD, Figure 5-2
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
我想,这是一个哲学问题.
C语言有一组标准的逐位运算的,其中包括OR,AND,XOR,SHIFT LEFT/RIGHT,和NOT.为什么不旋转左/右旋转操作符或语言中包含的函数？
这些运算符与其他逐位运算符具有相同的复杂性,并且通常需要单个汇编指令,就像其他运算符一样.此外,我可以想到旋转运算符的很多用途,可能不会比xor运算符少 - 所以对我来说听起来有些奇怪,它们不包括在C中.
如果您确实需要使用C或C++进行旋转,那么有关于它的最佳实践的单独常见问题解答.关于这个问题的讨论是偏离主题的.
在汇编编程中,想要从寄存器的低位计算某些东西是相当普遍的,这些位不能保证将其他位置零.在像C这样的高级语言中,你只需将输入转换为小尺寸,让编译器决定是否需要分别将每个输入的高位归零,或者是否可以在输出之后切断结果的高位.事实.
这是为x86-64的(又名AMD64),出于各种原因尤其常见1,其中的一些是存在于其它的ISA.
我将使用64位x86作为示例,但目的是询问/讨论2的补码和无符号二进制算法,因为所有现代CPU都使用它.(注意,C和C++不保证两个补码4,并且有符号溢出是未定义的行为.)
作为示例,考虑一个可以编译为LEA指令2的简单函数.(在X86-64 SysV的(Linux)的ABI 3,前两个函数参数是rdi和rsi,与在返回rax. int是一个32位的类型.)
; int intfunc(int a, int b) { return a + b*4 + 3; }
intfunc:
lea eax, [edi + esi*4 + 3] ; the obvious choice, but gcc can do better
ret
gcc知道即使是负有符号整数,加法也只是从右到左,所以输入的高位不会影响进入的内容eax.因此,它保存了一个指令字节并使用 lea eax, [rdi + rsi*4 + 3]
为什么它有效？
1为什么x86-64频繁出现这种情况:x86-64有可变长度指令,其中额外的前缀字节改变了操作数大小(从32到64或16),因此在指令中通常可以保存一个字节.以相同的速度执行.当写入低8b或16b的寄存器(或稍后读取完整寄存器(Intel pre-IvB)时的失速)时,它也具有错误依赖性(AMD/P4/Silvermont):由于历史原因, …
在C采访中,我被要求将最后4位的数字的前4位交换掉.(例如,1011 1110应为1110 1011.)
有人有解决方案吗？
我正在尝试实现一个旋转左侧函数,它将整数x向左旋转n位
到目前为止我有这个:
int rotateLeft(int x, int n) {
return ((x << n) | (x >> (32 - n)));
}
我已经意识到不能为签名整数工作..任何人都有任何想法如何解决这个问题？
所以现在我试过了:
int rotateLeft(int x, int n) {
return ((x << n) | ((x >> (32 + (~n + 1))) & 0x0f));
}
并收到错误:
错误:测试rotateLeft(-2147483648 [0x80000000],1 [0x1])失败...... ...给出15 [0xf].应为1 [0x1]
我有一个问题如下所述:如何在没有嵌入式装配的情况下在C中执行旋转移位.更具体一点,如何旋转32位移位int.
我现在在类型的帮助下解决这个问题long long int,但我觉得它有点难看,想知道是否有更优雅的方法.
亲切的问候.
什么是最快的方法(在常见的现代架构上的cpu周期方面),len从位置开始生成位设置为1 的掩码pos:
template <class UIntType>
constexpr T make_mask(std::size_t pos, std::size_t len)
{
// Body of the function
}
// Call of the function
auto mask = make_mask<uint32_t>(4, 10);
// mask = 00000000 00000000 00111111 11110000
// (in binary with MSB on the left and LSB on the right)
另外,是否有任何编译器内在函数或BMI函数可以帮助？