你的浏览器版本过低,可能导致网站不能正常访问!
为了你能正常使用网站功能,请使用这些浏览器。

C编程面试题的多种解法

[复制链接]
gaosmile 发布时间:2020-4-27 16:50
问题描述
任意给定一个32位无符号整数n,求n的二进制表示中1的个数,比如n = 5(0101)时,返回2,n = 15(1111)时,返回4
这也是一道比较经典的题目了,相信不少人面试的时候可能遇到过这道题吧,下面介绍了几种方法来实现这道题,相信很多人可能见过下面的算法,但我相信很少有人见到本文中所有的算法。如果您上头上有更好的算法,或者本文没有提到的算法,请不要吝惜您的代码,分享的时候,也是学习和交流的时候。
普通法
我总是习惯叫普通法,因为我实在找不到一个合适的名字来描述它,其实就是最简单的方法,有点程序基础的人都能想得到,那就是移位+计数,很简单,不多说了,直接上代码,这种方法的运算次数与输入n最高位1的位置有关,最多循环32次。
int BitCount(unsigned int n)$ f2 ^( ^  D2 t0 ?# M" `: ]7 a& u
{# W- S+ N' o) F* M
    unsigned int c =0 ; // 计数器
& c3 D& y# v! G4 l    while (n >0)
0 ~( [1 P9 k. J5 V& i- c$ h    {% T* R% ^7 A& t; a
        if((n &1) ==1) // 当前位是1
: u# O, i- H4 T* V' W8 Q            ++c ; // 计数器加1
  u6 ]* k$ A; e# g- P+ k        n >>=1 ; // 移位
# b( ]* {# h& \. H! D( i    }5 }1 K% [, h9 }# J1 k0 p1 o
    return c ;
) O4 Z+ ?4 l$ b$ M# H}

. E. g& Z: r$ D4 h" r) z+ G
一个更精简的版本如下
int BitCount1(unsigned int n)( N' B* B; W$ h$ h" ]- N
{
: U% `! E" _* ]/ c    unsigned int c =0 ; // 计数器
" A9 T, Q" [& e5 v( z# i    for (c =0; n; n >>=1) // 循环移位
6 {' k$ d7 J! q) w5 |        c += n &1 ; // 如果当前位是1,则计数器加1
, m0 \8 G) `, D7 |    return c ;
2 ~5 K9 }% C  \  c: n  i4 P7 g9 E) G}

+ C& v3 D) W! ?, W' A问:如果输入参数是int,这种方法还能奏效吗?
如何修改?看看下面的方法:
int BitCount(int n), `1 v% q" G3 j) E4 R0 F
{
* H/ W) {9 r+ S# y: T    int num = 0;
! `9 f/ G9 J, L0 y' r/ W; J; @    unsigned int flag = 1;6 F6 C+ Y7 U& O
    while(0 != flag)
: B8 F7 X; x( K& N8 P    {8 k$ k" n  e9 h' C: z
        if(n & flag)# R1 z9 e1 f+ ~( [$ S: h
            num++;
6 u, B; v6 E& U        flag = flag << 1;
5 `/ a6 r; V0 o4 z6 a0 x    }
% O1 o1 r" S+ `5 `    return num;. `, Q+ Z, F' E; Q- k+ r( D" }
}
. [# @/ b3 ~- g$ X
3 M5 R; q& x& _2 q" ?% d" W8 h
快速法
这种方法速度比较快,其运算次数与输入n的大小无关,只与n中1的个数有关。如果n的二进制表示中有k个1,那么这个方法只需要循环k次即可。其原理是不断清除n的二进制表示中最右边的1,同时累加计数器,直至n为0,代码如下
int BitCount2(unsigned int n)
# O! Y/ z! m* ]6 d8 m/ J" M{
; o0 Z5 \$ q  G8 x, i    unsigned int c =0 ;
2 A+ m% \0 Y4 |4 t6 f    for (c =0; n; ++c)
4 n9 B( O0 L5 g* x4 N  C    {
% ]1 g3 I) v0 V% P        n &= (n -1) ; // 清除最低位的1
7 s5 z$ s( G) F' Z% t    }
6 J) Q, [4 |; q2 R3 _    return c ;( S; P9 X- T, j/ [& C& n# L5 W# ]! E
}
) |: T$ C4 @- J' O( ^+ U+ A
为什么n &= (n – 1)能清除最右边的1呢?因为从二进制的角度讲,n相当于在n - 1的最低位加上1。举个例子,8(1000)= 7(0111)+ 1(0001),所以8 & 7 = (1000)&(0111)= 0(0000),清除了8最右边的1(其实就是最高位的1,因为8的二进制中只有一个1)。再比如7(0111)= 6(0110)+ 1(0001),所以7 & 6 = (0111)&(0110)= 6(0110),清除了7的二进制表示中最右边的1(也就是最低位的1)。
查表法动态建表
由于表示在程序运行时动态创建的,所以速度上肯定会慢一些,把这个版本放在这里,有两个原因
  • 介绍填表的方法,因为这个方法的确很巧妙。
  • 类型转换,这里不能使用传统的强制转换,而是先取地址再转换成对应的指针类型。也是常用的类型转换方法。
    & W/ T/ n5 @, R5 y
int BitCount3(unsigned int n) $ u  ~3 H7 W. c7 Y! I
{ 0 h8 m' C0 {) }) w! V$ t
    // 建表3 k; y% C% e6 c8 E
    unsigned char BitsSetTable256[256] = {0} ;
$ g0 B; v; ~( h: p: u- y) c% W% F9 ^$ R- F8 Z, h, a9 R  G' ]
    // 初始化表 + ]; H( H; m. A* |; T5 Y) p, U2 U
    for (int i =0; i <256; i++)
5 ?$ ]2 P" t0 M6 D    { : _) s  o7 O" j' {+ Z( D+ T
        BitsSetTable256 = (i &1) + BitsSetTable256[i /2];
7 |* M: S9 h0 I4 D8 m) E    }
  o- _2 ]4 S+ Z- w5 k' P+ ~
1 M6 P) s; U5 N    unsigned int c =0 ; # Q# V' F# ]( r

1 O2 G, \& F# z. G    // 查表
% P0 m4 x4 u- Y. z) D    unsigned char* p = (unsigned char*) &n ; 3 M9 H; e. p3 {$ G( o

+ ~( p" @# q9 x: t: N5 o    c = BitsSetTable256[p[0]] + + B% G) `3 @6 \+ A& ]& R
        BitsSetTable256[p[1]] +
) l, Y$ h: _. p0 l8 N& F        BitsSetTable256[p[2]] + - V' L8 u; w* Y
        BitsSetTable256[p[3]]; 3 p: ?6 i: ?0 d, ]

2 J) y6 W3 R3 [    return c ; 2 _  ]) A2 l4 v# K
}
* i3 r  O" |8 L5 c# r# C
先说一下填表的原理,根据奇偶性来分析,对于任意一个正整数n
1.如果它是偶数,那么n的二进制中1的个数与n/2中1的个数是相同的,比如4和2的二进制中都有一个1,6和3的二进制中都有两个1。为啥?因为n是由n/2左移一位而来,而移位并不会增加1的个数。
2.如果n是奇数,那么n的二进制中1的个数是n/2中1的个数+1,比如7的二进制中有三个1,7/2 = 3的二进制中有两个1。为啥?因为当n是奇数时,n相当于n/2左移一位再加1。
再说一下查表的原理
对于任意一个32位无符号整数,将其分割为4部分,每部分8bit,对于这四个部分分别求出1的个数,再累加起来即可。而8bit对应2^8 = 256种01组合方式,这也是为什么表的大小为256的原因。
注意类型转换的时候,先取到n的地址,然后转换为unsigned char*,这样一个unsigned int(4 bytes)对应四个unsigned char(1 bytes),分别取出来计算即可。举个例子吧,以87654321(十六进制)为例,先写成二进制形式-8bit一组,共四组,以不同颜色区分,这四组中1的个数分别为4,4,3,2,所以一共是13个1,如下面所示。
10000111 01100101 01000011 00100001 = 4 + 4 + 3 + 2 = 13
静态表-4bit
原理和8-bit表相同,详见8-bit表的解释
int BitCount4(unsigned int n)3 m3 g) Q4 b  U
{
5 k8 a. m9 y- W* a( ]    unsigned int table[16] =
+ ^% i; w" ^: c! E/ @    {7 h7 U7 j) l3 Q7 t8 a( e
        0, 1, 1, 2,
* w1 D- l3 R3 W5 y% A6 b        1, 2, 2, 3,
5 n/ G# _& H2 B, ]9 M; e  T        1, 2, 2, 3,
7 [% I* o' y9 l+ z! o        2, 3, 3, 4) X, t8 Q, c5 M: F7 h8 R) u
    } ;
0 m+ _! q9 Q4 z( G! p3 v# @8 w& n5 y4 {
    unsigned int count =0 ;  F% c& O. p3 o/ f
    while (n)4 v# a3 ^1 t' @9 W* u; I
    {) G- h5 H4 |- \! u! k4 e, K
        count += table[n &0xf] ;/ M3 s0 M' @1 k8 p) X) e5 W
        n >>=4 ;
4 o& p+ d; @2 T2 }    }
- k: k3 v; z9 L( Y, @4 R) M- P& o    return count ;
. h5 A1 E# @$ K4 L- b}
$ _, D8 s: `! z8 ~8 S
静态表-8bit
首先构造一个包含256个元素的表table,table即i中1的个数,这里的i是[0-255]之间任意一个值。然后对于任意一个32bit无符号整数n,我们将其拆分成四个8bit,然后分别求出每个8bit中1的个数,再累加求和即可,这里用移位的方法,每次右移8位,并与0xff相与,取得最低位的8bit,累加后继续移位,如此往复,直到n为0。所以对于任意一个32位整数,需要查表4次。以十进制数2882400018为例,其对应的二进制数为10101011110011011110111100010010,对应的四次查表过程如下:红色表示当前8bit,绿色表示右移后高位补零。
第一次(n & 0xff)          10101011110011011110111100010010
第二次((n >> 8) & 0xff)  00000000101010111100110111101111
第三次((n >> 16) & 0xff)00000000000000001010101111001101
第四次((n >> 24) & 0xff)00000000000000000000000010101011
int BitCount7(unsigned int n)1 p' H& @7 T; @
{
6 E8 U( H7 f  _5 z- S    unsigned int table[256] =
" ?% E; u: r9 A6 m- l5 |; L    { ) p) ^. O" W2 O) n$ B
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
/ H# R4 ^; O# E) ^        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
7 L, Y# [: l+ V/ D5 O! B        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
% ?. _/ \& y. v2 n        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, : k# n9 R" k  F- Y+ B
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
; _" C3 {6 N( O* {, J; x        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
4 @  m4 u  [1 E% l* \        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
: t) |& Z* r& k( W/ h( A$ i        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
. y, Y8 F1 q* l. _& r3 d) N        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 3 b7 h" A" A: }% K' N% X
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
" A, s2 \8 V1 r0 h* E# A6 o        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
7 E1 s' n; K2 r, f9 g        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1 |; ~' N# W& v        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  K. @. F# H3 [. Q1 T* R        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
0 M( l3 T: d( _+ ^5 a        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, ( t4 f. W2 o: E+ U3 h& M
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
) a" N  g; U- Z7 @9 }6 k0 ~    }; 0 Q; Q* w, A' J

' k9 M7 I# `$ G9 k* f% d; l2 G    return table[n &0xff] +% T9 f2 ^' v- v1 W: M$ X6 d; t
        table[(n >>8) &0xff] +0 u: S! T& }% `7 l% H" X) ~$ \
        table[(n >>16) &0xff] +( m* C7 L  i; P& w
        table[(n >>24) &0xff] ;/ f2 Y7 p3 Z1 a+ E; c( V
}
2 `% h4 l, X* l/ f4 L5 Y
当然也可以搞一个16bit的表,或者更极端一点32bit的表,速度将会更快。
平行算法
网上都这么叫,我也这么叫吧,不过话说回来,的确有平行的意味在里面,先看代码,稍后解释
int BitCount4(unsigned int n)
  f  O" r& ?3 O1 r3 W3 [  m- r{
. u: k/ [5 [3 a3 e8 C( a" n7 f    n = (n &0x55555555) + ((n >>1) &0x55555555) ; " a, x6 {: W) k/ s
    n = (n &0x33333333) + ((n >>2) &0x33333333) ;
/ q& G6 ^* j$ o0 x* L, }8 R+ v( p' \    n = (n &0x0f0f0f0f) + ((n >>4) &0x0f0f0f0f) ; ! t" n( X+ L% p
    n = (n &0x00ff00ff) + ((n >>8) &0x00ff00ff) ; : l/ a" I: N( C0 _
    n = (n &0x0000ffff) + ((n >>16) &0x0000ffff) ; 0 t1 X& o& l/ X5 f. I: D4 B$ g% M- }
) U8 t3 V: }9 G7 k5 q+ N
    return n ; 1 d" W3 Q9 i# u! \
}

: G# b7 L5 O1 Z# }0 h4 j( B* Z
速度不一定最快,但是想法绝对巧妙。说一下其中奥妙,其实很简单,先将n写成二进制形式,然后相邻位相加,重复这个过程,直到只剩下一位。
以217(11011001)为例,有图有真相,下面的图足以说明一切了。217的二进制表示中有5个1
完美法int BitCount5(unsigned int n)
/ u! L4 x) D: O! X1 E{
  t' x1 `5 u* ]* @5 g* v    unsigned int tmp = n - ((n >>1) &033333333333) - ((n >>2) &011111111111);
+ H/ E$ v# i' U9 K' \- I    return ((tmp + (tmp >>3)) &030707070707) %63;3 s/ i7 ?- ]# z9 N  A$ s9 |
}
! }5 v" e9 f- G1 r7 J1 {
最喜欢这个,代码太简洁啦,只是有个取模运算,可能速度上慢一些。区区两行代码,就能计算出1的个数,到底有何奥妙呢?为了解释的清楚一点,我尽量多说几句。
第一行代码的作用
先说明一点,以0开头的是8进制数,以0x开头的是十六进制数,上面代码中使用了三个8进制数。
将n的二进制表示写出来,然后每3bit分成一组,求出每一组中1的个数,再表示成二进制的形式。比如n = 50,其二进制表示为110010,分组后是110和010,这两组中1的个数本别是2和3。2对应010,3对应011,所以第一行代码结束后,tmp = 010011,具体是怎么实现的呢?由于每组3bit,所以这3bit对应的十进制数都能表示为2^2 * a + 2^1 * b + c的形式,也就是4a + 2b + c的形式,这里a,b,c的值为0或1,如果为0表示对应的二进制位上是0,如果为1表示对应的二进制位上是1,所以a + b + c的值也就是4a + 2b + c的二进制数中1的个数了。举个例子,十进制数6(0110)= 4 * 1 + 2 * 1 + 0,这里a = 1, b = 1, c = 0, a + b + c = 2,所以6的二进制表示中有两个1。现在的问题是,如何得到a + b + c呢?注意位运算中,右移一位相当于除2,就利用这个性质!
4a + 2b + c 右移一位等于2a + b
4a + 2b + c 右移量位等于a
然后做减法
4a + 2b + c –(2a + b) – a = a + b + c,这就是第一行代码所作的事,明白了吧。
第二行代码的作用
在第一行的基础上,将tmp中相邻的两组中1的个数累加,由于累加到过程中有些组被重复加了一次,所以要舍弃这些多加的部分,这就是&030707070707的作用,又由于最终结果可能大于63,所以要取模。
需要注意的是,经过第一行代码后,从右侧起,每相邻的3bit只有四种可能,即000, 001, 010, 011,为啥呢?因为每3bit中1的个数最多为3。所以下面的加法中不存在进位的问题,因为3 + 3 = 6,不足8,不会产生进位。
tmp + (tmp >> 3)-这句就是是相邻组相加,注意会产生重复相加的部分,比如tmp = 659 = 001 010 010 011时,tmp >> 3 = 000 001 010 010,相加得
001 010 010 011
000 001 010 010

001 011 100 101
011 + 101 = 3 + 5 = 8。(感谢网友Di哈指正。)注意,659只是个中间变量,这个结果不代表659这个数的二进制形式中有8个1。
注意我们想要的只是第二组和最后一组(绿色部分),而第一组和第三组(红色部分)属于重复相加的部分,要消除掉,这就是&030707070707所完成的任务(每隔三位删除三位),最后为什么还要%63呢?因为上面相当于每次计算相连的6bit中1的个数,最多是111111 = 77(八进制)= 63(十进制),所以最后要对63取模。
位标志法
感谢网友 @gussing提供
struct _byte ) f( C8 ~& e' B- N- s
{ 9 y2 f4 P2 Z! C% n- A' U$ e$ ~
    unsigned a:1; 2 q3 W0 N' L2 w; y1 K" y- ?
    unsigned b:1; 0 M: n- [- \/ L+ f, C8 q4 v
    unsigned c:1;
4 R' v& B6 g+ P8 X    unsigned d:1;
( ?. c9 I- k$ X0 x    unsigned e:1;
2 Z' K' A: J/ j, D* h2 J    unsigned f:1; + M/ `5 {' I" u$ v$ m, B" m
    unsigned g:1;
. f/ V* @8 v  Y) B; U    unsigned h:1; + l( c/ ~# U8 l
};
$ B1 |1 c( N; |9 @7 D/ @2 z1 l; n) ^0 H
long get_bit_count( unsigned char b ) . ^) i! P' e; w9 n& w. m: K' K! i
{
% N" j2 }# |- h8 Z    struct _byte *by = (struct _byte*)&b;
% I0 [2 L2 h6 V    return (by->a+by->b+by->c+by->d+by->e+by->f+by->g+by->h); - y( k: y: W6 }$ R# ^) S
}
赞 收藏 评论3 发布时间:2020-4-27 16:50

举报

3个回答
goyhuan 回答时间:2020-4-27 18:09:14
强  
李康1202 回答时间:2020-4-27 18:48:20
强!
a316363723 回答时间:2020-4-29 15:36:25
这个字体看的眼睛很难受,感觉眼睛跟着字体歪了一样。
关于
我们是谁
投资者关系
意法半导体可持续发展举措
创新与技术
意法半导体官网
联系我们
联系ST分支机构
寻找销售人员和分销渠道
社区
媒体中心
活动与培训
隐私策略
隐私策略
Cookies管理
行使您的权利
官方最新发布
人形机器人运动控制、感知与智能配电
半导体创新技术与应用方向
EE架构与软件定义汽车
12V/48V 汽车智能配电(SPD)
区域控制单元(ZCU)与分区架构
关注我们
st-img 微信公众号
st-img 手机版