任何一个非负整数，都有一个唯一的 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
到此这篇uchar i（uchar I for(i=0;i＜120,i++)什么意思）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/cjjbc/24380.html