uchar i（uchar I for(i=0;i＜120,i++)什么意思）

科技前沿 • 2025-05-16 13:53 • 阅读 37

大家好，我是讯享网，很高兴认识大家。

 <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg>

讯享网

‍

任何一个非负整数，都有一个唯一的 NAF (Non-adjacent form) 表示。

因着课程的缘由，我不得不研究一下 NAF 是怎么实现的，也是现学现用。

‍

Note:

‍

采用 C++ 实现
一篇很短的博客，专注于 2-NAF

‍

[toc]

‍

NAF 是一种二进制符号的表示形式，定义为：

$$n=sum_{i=0}^{i}d_{i}2^{i},d_{i}inleftlbrace-1,0,1 ight brace,forall iinleftlbrace0,1,2,ldots,k-1 ight brace,d_{i}cdot d_{i+1}=0$$

说人话就是就是没有两个相邻的非零系数。

naf的原理是下面这个等式：

$$2^{i}+2^{i-1}+cdots+2^{j}=2^{j+1}-2^{i}$$

这样一来，原来整数的二进制中的连续为1的表示，如{1,0,0,1,1,1,1}，就可以转化为{1,0,1,0,0,0,-1}了。

‍

V1，最low实现

‍

讯享网

‍

讯享网

这是一个简单的实现，为什么说很 low ？因为存在大量的边界检查，还必须要先将 N 转化为完整的2进制表示后才能处理。不行啊，就不能边转化边处理吗？

有了，假如......

‍

V2，位运算

‍

假如，我们只聚焦两位呢，因为事实上，我们确实只需要关注两个bit位，如果组合为 (11)b，那么我们就要将其变成 (100)b，放一个 -1 进naf，如果组合为 (01)b，那么我们就要将其变成 (00)b，放一个 0 进naf，如果为 (10)b 或者 (00)b，则放一个 0 进naf即可。

为什么这样做呢？

前面我们提到了 naf 的原理，本质上就是要检查有无 (11)b 这样的表示，也就是检查两个 bit 位即可。

‍

事实上，这样的实现还是不够好，为什么呢，因为有个碍眼的循环，假使没有这个循环就好了......

‍

V3, 打破循环

‍

前面我们提到，如果组合为 (11)b，那么我们就要将其变成 (100)b，那么只需要给末位加上一个1，不就可以自动实现了吗？

‍

讯享网

‍

但是呢，实现还是不够优雅，有些太长了，每次要单独看看两位 bit 位，如果说，我们能直接判断是不是(11)b,(10)b,(01)b,(00)b这样的组合就好了......

‍

V4，直接一次判断两位的组合

‍

我们重新梳理一下逻辑：

‍

(11)b->(100)b->(10)b
(10)b|(00)b->(1)b|(0)b
(01)b->(00)b

‍

(10)b|(00)b 对应的是什么呢？是偶数，也就是 n & 1 0 的情况，与之相对的 (11)b 和 (01)b 则对应 n & 1 1，那么，我们只需要......

‍

但是我还是不满足，我觉得那个flag的分支判断比较碍眼，能不能也优化掉呢？比方说不判断，直接放相应的计算值就行了。

假如......

‍

V5，消灭分支

‍

既然 N & 3 为 3 的时候放 -1 进去，N & 3 为 1 的时候放 1 进去，什么数与 1 差为 1，与 3 差为 -1 呢？

答案是 2。

然后，放 1 进去，N 要减 1，放 -1进去，N要减去(-1)。

那么，我们可以这样优化......

‍

讯享网

‍

想了想，如果一次移动两位，则要考虑 N 能不能移两位，感觉目前已经是最优解（大概）了，就此结束。

‍

NULL

‍