Chinaunix首页 | 论坛 | 博客
  • 博客访问: 164255
  • 博文数量: 154
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1575
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-20 17:02
  • 认证徽章:
文章分类

全部博文(154)

文章存档

2017年(112)

2016年(42)

我的朋友

分类: Java

2017-01-03 14:13:52

在并行计算和图形图像等处理中,经常会遇到一类叫做"下个2的幂"的问题,简单说来就是给定一个数,需要找到满足如下条件的一个数:
1. 最靠近这个数 
2. 大于或等于这个数 
3. 是2的N次方

简单函数描述就是
int nextPowerOfTwo(int num);

首先想到的一般算法可能是:

 int nextPowerOfTwo(int num)
 { int npot = 1; while( npot < num ) npot <<= 1; return npot;      
 } 

但明显上述实现随着num的增大,时间就会成倍上升!

有没有什么好办法呢?答案当然是:有

这里给出了一个优雅的改进算法:
http://acius2.blogspot.com/2007/11/calculating-next-power-of-2.html

下面是稍加改动后的一个实现

int nextPowerOfTwo(int num)
{ if (0 == num--) return 1;
    } num = (num >> 1) | num; num = (num >> 2) | num; num = (num >> 4) | num; num = (num >> 8) | num; num = (num >> 16) | num; //num = (num >> 32) | num;//如果是64位机器则需要增加一次计算 return ++num;           
} 

这个算法妙就妙在无论这个数多大,只要进行5次右移并或的操作(32位)就够了,堪称精妙!
原理原文有述,简单来说就是通过移位然后与原值进行或操作使得1的位成倍增加,因为是32位,所以重复进行5次1就覆盖了所有位(2的5次方),原例子不太直观,这里再举个例子说明:

假设给定的数是65537,那么
65537 - 1 = 65536
写成二进制形式:

0000 0000 0000 0001 0000 0000 0000 0000 1 0000 0000 0000 0000 1000 0000 0000 0000 //右移1位 0000 0000 0000 0001 1000 0000 0000 0000 //与原值或 ,1的位数翻倍 2 0000 0000 0000 0000 0110 0000 0000 0000 //右移2位 0000 0000 0000 0001 1110 0000 0000 0000 //与原值或,1的位数再翻倍 3 0000 0000 0000 0000 0001 1110 0000 0000 //右移4位 0000 0000 0000 0001 1111 1110 0000 0000 //与原值或,1的位数再翻倍 4 0000 0000 0000 0000 0000 0001 1111 1110 //右移8位 0000 0000 0000 0001 1111 1111 1111 1110 //与原值或,1的位数再翻倍 5 0000 0000 0000 0000 0000 0000 0000 0001 //右移16位 0000 0000 0000 0001 1111 1111 1111 1111 //与原值或,1的位数再翻倍 +1 0000 0000 0000 0010 0000 0000 0000 0000 // 131072 

眼尖的同学对比下原文的例子可能会发现某些数(比如947这个数)并不需要循环5次1就已经占位满了,这里再贴下947的一个重复过程:

0000 0011 1011 0011 0000 0011 1111 1011 0000 0011 1111 1111 //...with the remaining steps staying at this value. 

恩,在允许范围内有部分数其实不需要重复完5次,我特别实验了一下,比如在4096(可能还可以更大,有兴趣同学可以进一步验证下)范围内,只要重复4次就已经满足要求!这有什么意义呢,比如你给定的数能够确定在某一个范围,那完全可以减少重复次数!特别的,比如GL中纹理的尺寸一般不可能很大,这时就可以减少一次重复!5次减少一次,大约相当于减少五分之一!


阅读全文请点击:http://click.aliyun.com/m/8942/


阅读(246) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册