【C/C艹】使用位运算实现常用的整数运算

YY菌

　　众所周知，硬件底层仅支持位运算，所有高级运算均基于位运算组合实现。那么，如何利用基本位运算构造常用的整数运算（如加减乘除、乘方）呢？本文以SSE指令集为例，封装128位无符号整数的常用数学运算。之所以选择SSE，是因为它虽然提供了8位、16位、32位、64位的向量运算指令，却缺乏对128位大整数的直接算术支持；而其位运算恰好支持完整的128位操作。因此，我们可以用SSE的位运算模拟实现加减乘除及乘方，既填补了128位整数运算的空白，又便于阐述位运算构建高级运算的原理。目前实现仅限于无符号128位整数，暂不考虑有符号情况，以降低复杂度，方便初学者理解。

先直接上代码（需回帖可见）：

游客，如果您要查看本帖隐藏内容请回复

再上一个简单的测试代码：

int main()
{
        char buf[40];
        __m128i mi = _mm_cvtascii_si128("123456789098765432101234567890987654321");
        int len = _mm_cvtsi128_ascii(mi, buf);
        puts(buf);
        len = _mm_cvtsi128_ascii(_mm_set1_epi32(-1), buf);
        puts(buf);
        return 0;
}

正确的输出结果为：
123456789098765432101234567890987654321
340282366920938463463374607431768211455

现在来讲解一下原理和用法吧：

函数用途	函数原型	函数用法	实现原理
128位整数加法	__m128i _mm_add_si128(register __m128i l, register __m128i r) noexcept	128位和 = _mm_add_si128(128位被加数, 128位加数)	使用异或做当前位的加法，与做进位检测，如果有进位就继续加下去。
128位整数减法	__m128i _mm_sub_si128(register __m128i l, register __m128i r) noexcept	128位差 = _mm_sub_si128(128位被减数, 128位减数)	使用异或做当前位的减法，与非做借位检测，如果有借位就继续减下去。
128位整数乘法	__m128i _mm_mul_si128(register __m128i l, register __m128i r) noexcept	128位积 = _mm_add_si128(128位被乘数, 128位乘数)	把乘数拆分为多个2的整数幂，再对被乘数做相对应的位移，最后将所有位移结果相加。
128位整数除法	NTSTATUS _mm_div_si128(register __m128i l, register __m128i r, register __m128i *quot = nullptr, register __m128i *rem = nullptr) noexcept	异常代码 = _mm_div_si128(128位被除数, 128位除数, &128位商, &128位余数)        // 商和余数参数均可选，方便大多数时候只取商或只取余数	不断使用被除数减去除数，通过减法溢出测试被除数和除数的大小关系，最终减去次数就是商，被减后的被除数就是余数。
128位整数乘方	__m128i _mm_pow_si128(register __m128i l, register __m128i r) noexcept	128位幂 = _mm_pow_si128(128位底数, 128位指数)	使用非递归二分法实现对数复杂度的累乘
128位整数乘方	__m128i _mm_powi_si128(register __m128i l, register unsigned r) noexcept	128位幂 = _mm_powi_si128(128位底数, 32位指数)	原理同上，考虑到底数大于1的时候，指数最多128就必定溢出了，因此正常情况下指数不会太大，使用基本整数的概率更大，单独实现一个更高效的版本。
ASCII字符串转128位整数	__m128i _mm_cvtascii_si128(const char *text, const char *end = nullptr) noexcept	128位整数 = _mm_cvtascii_si128(字符串起始地址, 字符串结束地址)        // 结束地址可选，不传默认为nullptr，表示以\0字符结束，否则按end参数的位置结束。	每遍历一个字符串中的十进制位就累乘10并加上该位数
128位整数转ASCII字符串	__m128i _mm_cvtunicode_si128(const wchar_t *text, const wchar_t *end = nullptr) noexcept	128位整数 = _mm_cvtunicode_si128(字符串起始地址, 字符串结束地址)        // 结束地址可选，不传默认为nullptr，表示以\0字符结束，否则按end参数的位置结束。	原理同上，但增加了Unicode全角字符的处理。
UNICODE字符串转128位整数	unsigned _mm_cvtsi128_ascii(__m128i v, char *text, char *end = nullptr) noexcept	输出长度 = _mm_cvtsi128_ascii(128位整数, 缓冲区起始地址, 缓冲区结束地址)        // 结束地址可选，不传默认为nullptr，表示无边界检查，否则按end参数进行边界检查。	循环除以10求余数得到十进制结果并转换为字符串。
128位整数转UNICODE字符串	unsigned _mm_cvtsi128_unicode(__m128i v, wchar_t *text, wchar_t *end = nullptr) noexcept	输出长度 = _mm_cvtsi128_unicode(128位整数, 缓冲区起始地址, 缓冲区结束地址)        // 结束地址可选，不传默认为nullptr，表示无边界检查，否则按end参数进行边界检查。	原理同上，但结果是Unicode文本。

tlwh163

本地隐藏内容