关灯

例4.35 关灯

一条街道上有无数盏灯,每盏灯有自己的独立开关.管理员找若干个人按顺序一个一个从街道的一侧进入,每个人看到亮着的灯就熄灭,直到看到第一盏关着的灯,将其点亮,完成任务.
如果所有的灯质量完好,那么第m个人走过后,有多少灯被点亮过?

分析:

灯的状态只有亮灭两种,我们用0表示灭,1表示亮,模拟10个人走过街灯的过程.

---

状态 — 灯的情况 — 被点亮过的灯数

• 初始的状态 — …00000000 — 0
• 第一人走过 — …00000001 — 1
• 第二人走过 — …00000010 — 2
• 第三人走过 — …00000011 — 2
• 第四人走过 — …00000100 — 3
• 第五人走过 — …00000101 — 3
• 第六人走过 — …00000110 — 3
• 第七人走过 — …00000111 — 3
• 第八人走过 — …00001000 — 4
• 第九人走过 — …00001001 — 4
• 第十人走过 — …00001010 — 4

---

可以看出,灯的状况恰好构成了一个二进制数.再进一步,被点亮过的灯数,恰好是这个二进制的位数(不含前导0).再联系每个人的编号发现,十进制编号恰好与二进制数对应.
至此,问题转化为求给定的数m所对的二进制数的位数.

#include <iostream>
using namespace std;
int main(){
    int m,num=0;
    cin>>m;
    do
    {
        num++;
        m>>=1;//位运算中的右移,m>>1相当于m/2
    }while(m!=0);
    cout<<num;
    return 0;
}