S.l.e!ep.¢%
像打了激速一样,以四倍的速度运转,开心的工作
简单、开放、平等的公司文化;尊重个性、自由与个人价值;
posts - 1098, comments - 335, trackbacks - 0, articles - 1
C++博客
::
首页
::
新随笔
::
联系
::
聚合
::
管理
位运算之美——用+,-和位运算实现整数除法和取模(一)
Posted on 2009-09-20 11:13
S.l.e!ep.¢%
阅读(3577)
评论(3)
编辑
收藏
引用
所属分类:
Algorithm
位运算之美——用+,-和位运算实现整数除法和取模(一)
今天看了一位师兄去年的笔经总结,其中有一题是“不许用%和/来实现求任意数除以3的余数”,我想考官的目的应该是想考察学生对位运算的熟悉程度吧,于是我把题目扩展成“只能用+,-和位运算实现整数除法(/)和取模(%)”,
注意:这里不能使用其它的库例程来辅助计算,如log,log10等
。在思考这道题目的过程中,我又涉及到了许多二进制相关的题目,如:
判断给定的整数是不是2的整数次幂
判断给定的整数是不是4的整数次幂
求给定整数的二进制表示中1的个数
求给定整数的二进制表示中0的个数
求给定整数的二进制表示中最高位1的位置
求大于等于给定整数的最小的2的整数次幂
求给定整数的二进制表示的有效位数
...
这些题目都是经典老题,频繁出现于各类笔试面试题中,除了能考察位运算外,还能考察应聘者能否给出创新的算法来更好地解决问题。可以说这些题目都不难,如果使用32位的int来表示整数的话,蛮力法都可以比较好地完成任务,但是如果想尽可能地提高效率,那就需要动一番脑经了。下面给出我对这些问题的整理和C++实现,并在此基础上给出原题(只能用+,-和位运算实现整数除法(/)和取模(%),下文都称为原题)的实现。
当然,从某种意义上讲,特别是从充分利用底层硬件的计算能力(利用特殊的cpu指令)来看,这些解法肯定不是最优的,希望大侠们多多指点。
还要说明的是,
下面各题的顺序是按照我在思考原题时的思维过程来安排的
,在给出原题的实现时会详细说明。
判断给定的整数是不是2的整数次幂
这应该是最简单的,利用最高位是1,其后所有位为0的特性,常数时间解决问题:
1
//
判断n是否是2的正整数冪
2
inline
bool
is_2exp(
unsigned
int
n)
3
{
4
return
!
(n
&
(n
-
1
));
5
}
求给定整数的二进制表示中1的个数
考虑到n-1会把n的二进制表示中最低位的1置0并把其后的所有0置1,同时不改变此位置前的所有位,那么n&(n-1)即可消除这个最低位的1。这样便有了比顺序枚举所有位更快的算法:循环消除最低位的1,循环次数即所求1的个数。此算法的时间复杂度为O(n的二进制表示中的1的个数),最坏情况下的复杂度O(n的二进制表示的总位数)。
1
//
计算n的二进制表示中1的个数
2
inline
int
count1(
unsigned
int
n)
3
{
4
int
r
=
0
;
5
while
(n)
6
{
7
n
&=
n
-
1
;
8
r
++
;
9
}
10
return
r;
11
}
既然有了求给定整数的二进制表示中1的个数的办法,那么想要
求给定整数的二进制表示中0的个数
就很简单了。事实上,在二进制中,完全可以把0和1看作是对称的两个对象,取反操作(~)可以任意的切换这两个对象,只要先对n进行一次取反,然后再用上述算法即能得到二进制表示中0的个数。首先看下面的代码:
1
//
计算n的二进制表示中0的个数
2
inline
int
count0_wrong(
unsigned
int
n)
3
{
4
int
r
=
0
;
5
n
&=
~
n;
6
while
(n)
7
{
8
n
&=
n
-
1
;
9
r
++
;
10
}
11
return
r;
12
}
不知大家有没有看出问题来?是的~操作符会把所有高位的都取反,而不是只把有效位取反,所以我们需要一个能保持高位不变的位取反操作,下面是我的实现,时间复杂度和求二进制表示中1的个数的算法相同,都与二进制表示中1的个数有关:
1
//
保持高位取反
2
inline
unsigned
int
negate_bits(
unsigned
int
n)
3
{
4
if
(n
==
0
)
return
1
;
5
unsigned int
r
=
0
, m
=~
n;
6
while
(n)
7
{
8
r
|=
(n
^
(n
-
1
))
&
m;
9
n
&=
n
-
1
;
10
}
11
12
return
r;
13
}
有了这个特殊的取反操作,求给定整数的二进制表示中0的个数的办法就简单了:
1
//
计算n的二进制表示中0的个数
2
inline
int
count0( unsigned
int
n)
3
{
4
int
r
=
0
;
5
n
=
negate_bits(n);
6
while
(n)
7
{
8
n
&=
n
-
1
;
9
r
++
;
10
}
11
return
r;
12
}
看到这里,聪明的读者肯定看出问题来了,其实我干了一件很蠢的事情。看看上述算法的时间复杂度,negate_bits花了O(n的二进制表示中
1
的个数),while循环计算取反后的n的二进制表示中1的个数,事实上就是O(n的二进制表示中
0
的个数),两部分加起来其实就是二进制表示总的有效位数,换句话说,这个算法是线性的,而事实上,我们完全可以先线性地求出这个总的有效位数,然后减去1的位数,即得到0的位数,根本不用费那么大劲去整个保持高位的取反操作,两者的时间复杂度在渐进意义上也是相同的。所以,我犯傻了,但是这里又引出另一个问题:
求给定整数的二进制表示的有效位数
上面提到了线性地求这个位数(下文记为m),即“循环右移1位,记录右移次数”,时间复杂度O(m)。但是我想,一看到这个题目,所有人的第一反应应该是
floor(log
2
(n))+1
吧,但是请注意,本文在一开始就规定了
“不能使用库例程”
,那么在这个限制下该怎么做呢?有没有比线性时间更好的算法呢?其实到目前为止我也没有什么特别好的算法,希望谁有什么精妙的算法能指点一下,不要打我。。。
1
//
求给定整数的二进制表示的位数,线性算法
2
int
count_bit_1(
unsigned
int
n)
3
{
4
int
r
=
0
;
5
while
(n)
6
{
7
n
>>=
1
;
8
r
++
;
9
}
10
return
r;
11
}
:
求大于等于给定整数的最小的2的整数次幂
首先是最简单的思路:求出n的二进制表示的总位数m,于是1<<m即为所求值,当然这里要排除n自身就是2的整数次幂的情况,复杂度O(m),实现如下:
1
//
求大于等于n的最小的2的正整数冪,方法1
2
//
时间复杂度O(n的二进制位长度)
3
unsigned int
high_2exp_1(
unsigned
int
n)
4
{
5
if
(n
<=
1
)
return
1
;
6
if
(is_2exp(n))
return
n;
7
8
unsigned
int
r
=
1
;
9
while
(n)
10
{
11
n
>>=
1
;
12
r
<<=
1
;
13
}
14
15
return
r;
16
}
事实上这就涉及到上面求二进制表示位数的问题,所以
目前为止
在此基础上的算法都是线性时间的。
那有没有不用计算位数m,从而效率更好的算法呢,能不能像在计算二进制表示中1的个数时那样根据1的个数来设计算法呢?回到那一题中,“n-1会把n的二进制表示中最低位的1置0并把其后的所有0置1”,那么n|=n-1就把n的二进制表示中最低位1后的所有0置1,再加上1,那么就把最低位1左移了一位。于是,便有了更好的算法:循环左移最低位的1,直到n是2的整数次幂。该算法跟二进制表示中的1个数和位置有关,最坏时间复杂度还是O(二进制表示位数),但是比起上一个实现,这个算法在多数情况下都比上一个算法快。实现如下:
1
//
求大于等于n的最小的2的正整数冪,方法2
2
//
计算时间与n的二进制表示中1的个数和位置有关,比方法1效率高
3
//
最坏情况下的时间复杂度与方法1相同
4
unsigned
int
high_2exp_2(
unsigned
int
n)
5
{
6
if
(n
<=
1
)
return
1
;
7
8
while
(
!
is_2exp(n))
9
{
10
n
|=
n
-
1
;
11
n
++
;
12
}
13
14
return
n;
15
}
最后来一个简单的扩充题目:
判断给定的整数是不是4的整数次幂
观察4的整数次幂的特征,容易发现除了满足n&(n-1)==0外,唯一的1位后的0的个数是偶数,这从4
x
=2
2k
也能简单地得到。这就很直观地衍生出一个简单的算法:
1
//
判断n是否是4的整数次幂
2
bool
is_4exp(unsigned
int
n)
3
{
4
if
(
!
is_2exp(n))
return
false
;
5
6
int
bit_len
=
count_bit_1(n)
-
1
;
//
线性时间求二进制位数
7
if
((bit_len
&
0x1
)
!=
1
)
8
return
true
;
9
else
10
return
false
;
11
}
算法很直观,但是比起is_2exp的常数时间is_4exp的线性时间总让我觉得不能接受,不过无奈还是没有想出好办法来,哎。。。求大牛指点啊
说明:写这篇文章,已经三次丢失全文了,把我快搞疯了,firefox下好像有点问题,先把文章发上来,过会儿换到IE下继续。。。
再说明:换了IE后就没再出问题了,不过写着写着发现写了好久,先歇会儿,得看书补习功课了
最后的说明:下次会基于上面的内容,给本文最初提出的问题(只能用+,-和位运算实现整数除法(/)和取模(%))的实现
Feedback
#
re: 位运算之美——用+,-和位运算实现整数除法和取模(一)
回复
更多评论
2010-10-25 10:20 by
yu
无意中逛到这里,惊喜之。
#
re: 位运算之美——用+,-和位运算实现整数除法和取模(一)
回复
更多评论
2010-11-18 16:06 by
zl
最后的说明:下次会基于上面的内容,给本文最初提出的问题(只能用+,-和位运算实现整数除法(/)和取模(%))的实现
在那里?
#
re: 位运算之美——用+,-和位运算实现整数除法和取模(一)
回复
更多评论
2011-09-25 12:03 by
skyworm
n &= ~n; // 写错啦,这个操作之后,n就永远等于0了。
刷新评论列表
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
TEA算法在QQ中的应用
Code01
c++MD5加密类
罗马计数法
位运算之美——用+,-和位运算实现整数除法和取模(一)
Int2Hex
n个数中有且仅有一个数出现了奇数次
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © S.l.e!ep.¢%
日历
<
2009年4月
>
日
一
二
三
四
五
六
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
公告
mail: sleepwom@163.com (每月一看)
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(5)
给我留言
查看公开留言
查看私人留言
随笔分类
(1107)
A·M·F·3(9)
Algorithm (8)
Axis(3)
Book(1)
C++(89)
COM(27)
Crack(39)
CURL(3)
Data Struct(1)
DataBase(14)
Delphi(1)
Design Pattern(11)
DirectUI(14)
DLL(2)
DOS(32)
emule
Encryption (4)
English(7)
epoll(8)
FastDB(10)
Finance(1)
Flash(9)
Game(8)
Game Design(1)
gdb(5)
GFW(1)
Haker
hardware
HTML(39)
ICE(8)
IE_BHO(1)
IM(2)
Inside Windows(2)
InstallShield (7)
Interview(12)
IOCP(19)
Lua(14)
Management(10)
Math(2)
Media(2)
Medical science(1)
MongoDB(4)
MSXML(1)
MulThreads(10)
NetWork(8)
Office Automation(5)
OpenSSL(13)
Oracle(1)
Other(61)
P2P(3)
PE(10)
Plan
ProjectSummary(4)
python(3)
Reactos(1)
Regular expression(2)
Reverse Engineering(5)
RootKit(116)
sed(1)
Server Program(3)
Shell(12)
Skynet(6)
SOAP(5)
SQLite(2)
SSL(3)
STL(3)
System Safe(1)
Team(9)
test(26)
TortoiseSVN(2)
UAC(3)
Unix(89)
Unknown(5)
VB(1)
VBScript(2)
VC(124)
Video Processing(1)
WIN7 + VC(3)
WinDbg(38)
Windows(13)
Windows WDM(61)
Windows扎记(1)
WTL(1)
yacc(3)
Z.E.R.O.M.Q(1)
生活常识(1)
网络协议(2)
系统低层(11)
随笔档案
(1098)
2015年1月 (1)
2014年12月 (9)
2014年11月 (18)
2014年6月 (1)
2014年4月 (2)
2013年9月 (1)
2013年5月 (10)
2012年7月 (3)
2012年4月 (2)
2012年3月 (8)
2012年2月 (6)
2012年1月 (13)
2011年12月 (2)
2011年11月 (3)
2011年10月 (5)
2011年8月 (3)
2011年7月 (8)
2011年6月 (6)
2011年5月 (12)
2011年4月 (28)
2011年3月 (15)
2011年2月 (10)
2011年1月 (16)
2010年12月 (21)
2010年11月 (16)
2010年10月 (6)
2010年9月 (17)
2010年8月 (19)
2010年7月 (25)
2010年6月 (21)
2010年5月 (38)
2010年4月 (10)
2010年3月 (24)
2010年2月 (58)
2010年1月 (78)
2009年12月 (29)
2009年11月 (35)
2009年10月 (152)
2009年9月 (130)
2009年8月 (24)
2009年7月 (2)
2009年6月 (4)
2009年5月 (14)
2009年4月 (31)
2009年3月 (24)
2009年2月 (30)
2009年1月 (45)
2008年12月 (24)
2008年11月 (23)
2008年10月 (16)
文章档案
(1)
2009年2月 (1)
相册
SimpleWord
随笔
收藏夹
(3)
Operation System(3)
Other
DataStruct
数据结构
数据结构
搜索
积分与排名
积分 - 1240041
排名 - 10
最新评论
1. re: linux信号Linux下Signal信号太详细了,终于找到了
写的不错。
--zsx
2. re: 汇编中的test和cmp比较
666666666
--xx
3. re: linux信号Linux下Signal信号太详细了,终于找到了
这篇文章就是个垃圾
--11
4. re: CreateService加载驱动过程
可以在内核太下直接调用这些函数来加载吗?
--peace
5. re: 在VC中彻底玩转Excel
怎样能够提高读写速度
--Touch
6. re: 函数开始处的MOV EDI, EDI的作用收藏
不错,谢谢分享。
--abc
7. re: gcc g++ 4.7 安装泪奔记(续)
最新已经到4.9.2了,还是用Archlinux好。。
--bigeast
8. re: ./lua/addtest.lua:9: attempt to index local 'testobj' (a userdata value)
c++对象导到lua之后成为了一个“userdata ”,原来上面的成员、方法都会访问不了的,只是一个普通的内存块,如果想用,要把方法也倒到Lua。
--陈冠希
9. re: 关于NoSQL,你必须知道的九件事
说的玄而又玄
--cpper
10. re: ./lua/addtest.lua:9: attempt to index local 'testobj' (a userdata value)
lua_touserdata() 不会改变堆栈
--网络兼职
11. re: lua中的closure
这不就是闭包嘛,没啥稀奇的吧。javascript也有 很多脚本语言都有
--evilwk
12. re: lua中的closure
lua有专有名词,叫upvalue
--Quon Lu
13. re: lua函数中的"匿名变量"?
_是用作占位符,表示参数不会使用
有时候函数调用者传入了多个参数,函数用不到的参数,可以用_占位
主要多见于一些回调函数
--Clear
14. re: lua函数中的"匿名变量"?
只是传递可变参数而已,这两个例子是结合演示可变参数吧
--南宫临风
15. re: lua函数中的"匿名变量"?[未登录]
占两个位置,意图何在?
--jcily
16. re: IOCP的一个简单封装类(zz) [转]
例子不能运行
--dsa
17. re: Flash CS3动作面板打开出错[Java运行时环境初始化时出现错误,你可能需要重...
不过我已经有java环境了,为什么还是需要安装呢?而且我想你说的那样做,只有900KB而已啊!怎么回事?
--Echo____g
18. re: The secret life of GetWindowText
评论内容较长,点击标题查看
--allen
19. re: Lua学习笔记
ECCDDFC08D2AE6DCD26DB8B09AE0F6264DFDA306
--xiaoxiao
20. re: 实用命令:利用openssl进行BASE64编码解码、md5/sha1摘要、AES/DES3加密解密 收藏
66F053665DF4F26C7CAA2DE22FBD1B51
--xiaoxiao
21. re: 虚拟键盘(软键盘)设计要点
博主 有个小bug不知道该怎么改
当点击完某个键的时候 时不时会出现 该键还遗留按下去的蓝色 回不到原本颜色
是和页面的刷新快慢有关吗?
非常感谢
--red
22. re: 虚拟键盘(软键盘)设计要点
非常感谢博主!正好要开发软键盘
--red
23. re: C语言中实现不同函数间jump的方法[未登录]
__asm{push 0}
替换为
_alloca(4)
--cpp
24. re: QQ2009 界面技术(DirectUI)
评论内容较长,点击标题查看
--xiaozhi_5638
25. re: sqlite 日期比较.取大于现在时间的记录
评论内容较长,点击标题查看
--威風
26. re: yacc学习笔记(1) 2013.05.11
《flex 与 bison(中文版)》
--coreBugZJ
27. re: yacc学习笔记(1) 2013.05.11
学习一下
--seahouse
28. re: Coroutines in C
mark
--zgpxgame
29. re: 突发奇想 之 远程调用
wcf
--三断笛
30. re: 突发奇想 之 远程调用
rpc
--Richard Wei
31. re: 突发奇想 之 远程调用
函数式编程,参考一下jquery的数据请求。
--漂漂
32. re: 突发奇想 之 远程调用
楼上的,我看了,系统API都有现成的,灰常不错,我喜欢.
--S.l.e!ep.¢%
33. re: 突发奇想 之 远程调用
楼主可以试试协程
--会飞的导弹猪
34. re: 突发奇想 之 远程调用
Lambda 表达式 可以缓解 用起来感觉不错的
--Lo
35. re: 用XML存储数据的缺陷,优势
@是大法官
顶~~~~~~~~
--幻想
36. re: P处理的双进程守护
评论内容较长,点击标题查看
--幻想
37. re: Windows下删除.svn文件夹的最简易方法
这想法好,每次explorer刷新一次都会去做一次,又学到了
--幻想
38. re: OPENSSL 生成 CERT 参考
REQ_DEPT_NAME 等 这些定义在哪? 最好把头文件都给列出来。谢谢!
--吕文华
39. re: DirectUI For WebBrowser
怎么解决IOleInPlaceSiteWindowless::InvalidateRect()无响应的?
--bluesky
40. re: 怎么让Firefox支持ActiveX控件
在 new ActiveXObject 在IE中可以发现在火狐中用什么来代替啊
--陈彦鑫
阅读排行榜
1. linux信号Linux下Signal信号太详细了,终于找到了(45103)
2. 实用命令:利用openssl进行BASE64编码解码、md5/sha1摘要、AES/DES3加密解密 收藏 (8690)
3. 汇编中的test和cmp比较(8590)
4. [转] DirectUI的初步分析(7897)
5. 如何用WinDbg定位内存泄露? (6749)
6. 调用OPENSSL读取PEM文件的灵异问题(6713)
7. 如何区分虚拟网卡与物理网卡(6627)
8. 在主线程中慎用WaitForSingleObject (WaitForMultipleObjects) (转)(6295)
9. 在VC中彻底玩转Excel(6261)
10. vc2005的诡异错误“Windows has triggered a breakpoint in .exe.”(6234)
11. sqlite 日期比较.取大于现在时间的记录(6226)
12. ./lua/addtest.lua:9: attempt to index local 'testobj' (a userdata value)(6202)
13. Linux遭遇Segmentation fault(5998)
14. 今天发现 EnterCriticalSection 里头还是调用了 WaitForSingleObject(5878)
15. 在vs2008中添加include文件和lib文件(5774)
16. shell bash模拟二维数组(5718)
17. DLL Inject -- 一、Windows 钩子(Hooks) - (1)(5648)
18. 静态代码分析工具汇总(5545)
19. lua动态链接库(luaopen_*函数的使用)(5454)
20. [转载]最好的53个 VC++ /MFC 开源软件项目(5437)
21. VC 操作 MDB 文件类(5377)
22. WSARecv 函数(5353)
23. gcc g++ 4.7 安装泪奔记.(5296)
24. HOOK钩子机制学习笔记(4) - 钩子函数说明 收藏 (5190)
25. 关于TCP丢包,断开的疑问(4951)
26. [转]VC++UDP实现可靠传输(文件)(虚拟TCP)((4908)
27. curl应用总结(一)(4832)
28. c和c++中取任意对数的简单方法(4809)
29. 【转】如何高效产生m个n范围内的不重复随机数(m<=n)(4715)
30. lua动态链接库之单个so文件包含多个模块(luaL_requiref函数的使用) (4562)
31. http协议 文件下载原理详解(4492)
32. 反调试技巧总结-原理和实现(4450)
33. set、vector、list和deque 顺序容器(4278)
34. xp下使用vista音量合成器(4262)
35. 如何合并两个vector?(4188)
36. std::tr1::shared_ptr 使用的一点体会 (4047)
37. 编码规范(4040)
38. CMake安装(3972)
39. 实现Sock5代理(转)(3968)
40. X.509 数字证书结构和实例 (3854)
评论排行榜
1. 工作两年后的总结(17)
2. [转载]最好的53个 VC++ /MFC 开源软件项目(12)
3. VMware虚拟机出现Reason: Failed to lock the file(转)(9)
4. 实现了一个写LOG类(9)
5. 封装了IOCP(8)
6. Thread Class(7)
7. 2009的计划(7)
8. Visual C++ 6 令我很晕(6)
9. 突发奇想 之 远程调用(6)
10. SimpleWord界面初稿3(5)
11. Simple Word界面初稿2(5)
12. 内存崩溃的BUG (2) (5)
13. 虚拟键盘(软键盘)设计要点 (5)
14. 内存崩溃的BUG (4) 完成端口的问题? 程序的BUG?(4)
15. 内存崩溃 CASE 3(4)
16. 今天发现 EnterCriticalSection 里头还是调用了 WaitForSingleObject(4)
17. 为了生成flash文件方便,写了个工具(4)
18. 代码坏味3(4)
19. 技术团队管理(一)(4)
20. 复杂的逻辑的BUG(4)
21. 单元测试工具在 MF C编程 中的使用问题 [转] (花了钱在网上下载的一篇文章,郁闷)(4)
22. 在主线程中慎用WaitForSingleObject (WaitForMultipleObjects) (转)(4)
23. 使用cppunit做c++单元测试(3)
24. 代码的坏味2(3)
25. 代码的坏味(3)
26. 关于TCP丢包,断开的疑问(3)
27. 位运算之美——用+,-和位运算实现整数除法和取模(一) (3)
28. 内存崩溃的BUG (3) (3)
29. 也谈 设计模式之Observer模式 (3)
30. MsgWaitForMultipleObjects 后遗症(3)
31. 86 Line 线程封装类 only for Win32(3)
32. QQ2009 界面技术(DirectUI) (3)
33. 写了个双向链表(3)
34. DLL Inject -- 一、Windows 钩子(Hooks) - (1)(3)
35. 突发的 XX Encoding(3)
36. CxImage类库(3)
37. lua函数中的"匿名变量"?(3)
38. lua中的closure(2)
39. ./lua/addtest.lua:9: attempt to index local 'testobj' (a userdata value)(2)
40. yacc学习笔记(1) 2013.05.11(2)