2011年3月27日星期日

x&(x-1)

来源: 原文链接


昨天在淘宝招聘会上遇到的这道笔试题:求下面函数的返回值 -- 统计1的个数

int func(int x)
{
    int countx = 0;
    while(x)
    {
        countx++;
        x = x&(x-1);
    }
    return countx;
}

假定x = 9999
10011100001111
答案: 8

思路: 将x转化为2进制,看含有的1的个数。
注: 每执行一次x = x&(x-1),会将x用二进制表示时最右边的一个1 变为0,因为x-1将会将该位(x用二进制表示时最右边的一个1)变为0。

判断一个数(x)是否是2的n次方
-------------------------------------

#include <stdio.h>

int func(int x)
{
    if( (x&(x-1)) == 0 )
        return 1;
    else
        return 0;
}

int main()
{
    int x = 8;
    printf("%d\n", func(x));
}

注:
(1) 如果一个数是2的n次方,那么这个数用二进制表示时其最高位为1,其余位为0。
(2) ==优先级高于&

运行级别及Ubuntu启动进入文本模式

Update 20111028 以前转载的内容可能只适用于某个版本(至少Ubuntu 9.10就不适用了),又找到一些方法,经试用可行,记录在此。 来源:ubuntu 开机启动终端 字符模式 文本模式 注意 debian类系统的启动级别和往常的redhat等不同 rc0表示关机rc6表示重启 rc1表示单用户模式 rc2-rc4表示多用户模式 ( 0 关机 1 单用户模式 2 不带网络的多用户模式 3 带网络的多用户,也就是所谓的纯字符模式 4 保留,用户可以自给定义 5 图形界面的多用户模式 6 重起系统 ) 所以如果你想要启动到终端的话 你只需要关闭gdm的服务 我介绍一个简单的方法 代码: sudo apt-get install sysv-rc-conf sudo sysv-rc-conf 然后在里面找到一个叫做gdm的服务,别且在所有级别关闭它 然后q就ok了 找到的第二种方法 用nano编辑 /etc/X11/default-display-manager,把/usr/sbin/gdm注释掉,即在前面加个#号,改成#/usr/sbin/gdm,然后在加一行false这样保存既可. 完整的是这样: #/usr/sbin/gdm false 修改后重启,这样启动就是字符界面了。 找到的第三种方法 # 0 - halt (Do NOT set initdefault to this) 关机(不要设置为默认) # 1 - Single user mode 单用户模式 # 2 - Multiuser, without NFS (The same as 3, if you do not have networking) 多用户模式,但不支持NFS # 3 - Full multiuser mode 完全的多用户模式 # 4 - unused 没用到 # 5 - X11 图形界面 # 6 - reboot (Do NOT set initdefault to this) 重启(不要设置为默认) RedHat中要改变启动级别,只要修改/etc/inittab。Ubuntu有点不一样,网上的方法也很多,试过其中一种。   You need to open the /etc/default/grub file, locate the following line:   GRUB_CMDLINE_LINUX_DEFAULT="quiet splash"   and change it to:   GRUB_CMDLINE_LINUX_DEFAULT="quiet splash text"   update-grub 即编辑/etc/default/grub文件,将GRUB_CMDLINE_LINUX_DEFAULT="quiet splash"改为GRUB_CMDLINE_LINUX_DEFAULT="quiet splash text",然后更新一下grub。 方法三还可以。如果想用这种方法永远启动到字符终端模式,则可以修改/boot/grub/grub.cfg,在相应的位置添加txt参照即可。但是grub.cfg是 自动生成的,所有的在里面的修改都可能被其它的操作覆盖掉,比如update-grub命令,如果不想被覆盖,则修改/etc/default/grub 把 GRUB_CMDLINE_LINUX_DEFAULT="quiet splash" GRUB_CMDLINE_LINUX="" 改成 GRUB_CMDLINE_LINUX_DEFAULT="text" GRUB_CMDLINE_LINUX="" 然后再运行一下update-grub命令,它会自动添加上text参数到内核参数中。 说明: 1,无论使用什么方式启动到字符终端模式,你都可以使用命令startx命令来启动Xwindow 2,在10.04 lucid 下测试成功 参数的含义(个人猜测,没有在网上找到相关内容) quiet 阻止内核输入到命令行 splash 显示启动画面,如ubuntu logo text 启动到字符终端模式 我的同时写上quiet 和text就起不来,停在checking battery status 下面不动了,也可以我为了测试等待的时间不够长,虽然不动了,可以按CTRL+ALT+DELETE重新启动。 文本与桌面模式切换: 文本模式登陆后,在普通用户权限下执行startx,进入到桌面模式。 一定要在普通用户权限下,root权限下startx,桌面模式都是默认设置,不加载个人设置! 桌面到文本的切换: Ctrl+Alt+F1,切到文本界面,执行Ctrl+c,结束掉刚才启动的X server!
以下为旧文 来源:未知 Linux系统有7个运行级别(runlevel)  (注意下文,debian系衍生的linux 运行级不一样) 运行级别0:系统停机状态,系统默认运行级别不能设为0,否则不能正常启动 运行级别1:单用户工作状态,root权限,用于系统维护,禁止远程登陆 运行级别2:多用户状态(没有NFS) 运行级别3:完全的多用户状态(有NFS),登陆后进入控制台命令行模式 运行级别4:系统未使用,保留 运行级别5:X11控制台,登陆后进入图形GUI模式 运行级别6:系统正常关闭并重启,默认运行级别不能设为6,否则不能正常启动 运行级别的原理: 1。在目录/etc/rc.d/init.d下有许多服务器脚本程序,一般称为服务(service) 2。在/etc/rc.d下有7个名为rcN.d的目录,对应系统的7个运行级别 3。rcN.d目录下都是一些符号链接文件,这些链接文件都指向init.d目录下的service脚本文件,命名规则为K+nn+服务名或S+nn+服务名,其中nn为两位数字。 4。系统会根据指定的运行级别进入对应的rcN.d目录,并按照文件名顺序检索目录下的链接文件      对于以K开头的文件,系统将终止对应的服务      对于以S开头的文件,系统将启动对应的服务 5。查看运行级别用:runlevel 6。进入其它运行级别用:init N 7。另外init0为关机,init 6为重启系统 ____________________________________________________________________________________________ 因为debian 系衍生出来的linux 一向是没有使用/etc/inittab 作为登入状态文档来使用的。但是虽然没有系统默认没有这个文件,但是你可以自己建一个inittab文件。 因为从/etc/event.d/中的rc-default文件中代码可以看出: script runlevel --reboot || true if grep -q -w -- "-s\|single\|S" /proc/cmdline; then telinit S elif [ -r /etc/inittab ]; then RL="$(sed -n -e "/^id:[0-9]*:initdefault:/{s/^id://;s/:.*//;p}" /etc/inittab || true)" if [ -n "$RL" ]; then telinit $RL else telinit 2 fi else telinit 2 fi end script 系统会首先搜寻inittab文件,如果不存在,那么将运行在2级别上。所以你可以自己建个inittab文件,或者把相应的telinit 2 改为 telinit X(你想要运行的级别) 转到kubuntu之前曾经学习了一下,了解到ubuntu在6.10开始用upstart替代init,主要脚本都在/etc/event.d下面,默认情况下/etc下没有inittab文件。 刚装上kubuntu时候专门到/etc/event.d下看了一下,特别注意到rc-default这个脚本,里面有一段内容: elif [ -r /etc/inittab ] then 说明默认情况下inittab虽然不存在,但是用户建立的inittab还是会被注意到的。然后又经别人的指点看了一下/usr/share/doc/upstart/下面的文档,其中README.Debian中有这么一段内容: 这就给我这样一个印象,即虽然ubuntu用upstart替代init,但还是和init保持兼容。 今天正好需要将系统直接启动到字符界面下,即不启动kdm。 edit the /etc/inittab file 那就试试自建一个inittab文件,并按照以前的习惯写入一行id:3:initdefault: ,保存后重新启动,结果发现毫无变化,依然启动到桌面,有点纳闷,难道inittab不起作用?在终端里输入runlevel检查当前状态,显示 N 3,说明inittab有效果,那是什么原因呢? 将刚才建立的inittab移除,将系统恢复到之前的状态并重新启动,再用runlevel检查,显示 N 2,说明ubuntu系统的default runlevel可能是2,这和我以前的常识有些冲突,看来又需要学习了。 先去分别查看/etc/rc2.d至rc5.d下的内容,发现基本一致,都启动了kdm。这与其他的linux发行版不太一致,通常runlevel 3是Multi user mode,即直接登录到字符界面;而runlevel 5是Multi user mode with GUI,即登录到图形界面。 后来在Debian的FAQ里面搜索到这样的内容: 0(halt the system) 1(single-user mode) 2through5(various muli-user modes),and 6(reboot the system) 小区别就在这里了,看来debian以及衍生出来的发行版,如ubuntu的default runlevel确实是2,而且id 2至5都是一样的。 真相大白,再次建立inittab,写入id:3:initdefault: ,然后进入/etc/rc3.d,重命名S30gdm,重新启动系统,如愿以偿进入字符界面。 

2011年3月23日星期三

在VC9.0中实现C++模板类头文件和实现文件分离的方法

来源:原文链接


如何实现C++模板类头文件和实现文件分离,这个问题和编译器有关。

引用<>里的观点:1)标准C++为编译模板代码定义了两种模型:“包含”模型和“分别编译”模型。2)所有编译器都支持“包含”模型

,某些编译器支持“分别编译”模型。

问题的提出:(帖子在:http://topic.csdn.net/u/20101215/15/f4f270f2-f0f9-4c5f-8765-1bfde2aeebbf.html)

第一种方法:按C++primer中的“包含”模型,在定义模板类的头文件中的末行用语句:#include "template_compile.cpp"

在类模板头文件template_compile.h中:


template  
class base
{
public:
    base() {};
    ~base() {};
    T add_base(T x,T y);
};
#include "template_compile.cpp"


在类模板的实现文件template_compile.cpp中:


template  
T base::add_base(T x,T y)  
{
    return x+y;
}


在使用模板的测试文件use_template.cpp中:

#include  
#include "template_compile.h"
using namespace std;
void main()
{
...
}


这种方法不能通过编译,"template_compile.cpp"文件不能"看见"“template_compile.h"文件。

然而:如果我把类模板的实现文件里代码放在类模板的头文件中,注释掉:#include "template_compile.cpp",编译和运行不会有任何错误。理论上”把类模

板的实现文件里代码放在类模板的头文件中“和”在定义模板类的头文件中的末行用语句:#include "template_compile.cpp" “是一致的,但编译器就是通不

过。

实验证明:VC9.0不支持C++primer中所说的“包含”模型。

第二种方法:bruceteen提出的:使用define

在类模板头文件template_compile.h中:


template  
class base
{
public:
  base() {};
  ~base() {};
  T add_base(T x,T y);
};
#define xxx
#include "template_compile.cpp"


在类模板的实现文件template_compile.cpp中:


#ifdef xxx
template  
T base::add_base(T x,T y)  
{
  return x+y;
}
#endif


测试文件不变。

实验证明:在VC9.0中,这种方法可以实现类模板头文件和实现文件的分离

方法三:

在类模板头文件template_compile.h中:


template  
class base
{
public:
    base() {};
    ~base() {};
    T add_base(T x,T y);
};


在类模板的实现文件template_compile.cpp中:


#include "template_compile.h"
template  
T base::add_base(T x,T y)  
{
    return x+y;
}


在使用模板的测试文件use_template.cpp中:使用#include "template_compile.cpp"


#include  
#include "template_compile.cpp"
using namespace std;
void main()
{
...
}


实验证明:在VC9.0中,这种方法可以实现类模板头文件和实现文件的分离。

另外实验证明:VC9.0不支持“分别编译”模型。

2011年3月21日星期一

“火柴棍式”程序员面试题

来源:原文链接




有时候,有些面试题是很是无厘头,这不,又有一个,还记得小时候玩的的"火柴棍游戏"吗,就是移动一根火柴棍改变一个图或字的游戏。程序面试居然也可以这么玩,看看下面这个火柴棍式的程序面试题吧。

下面是一个C程序,其想要输出20个减号,不过,粗心的程序员把代码写错了,你需要把下面的代码修改正确,不过,你只能增加或是修改其中的一个字符,请你给出三种答案。



int n = 20;
for(int i = 0; i < n; i--){
printf("-"); }

不要以为这题不是很难,我相信你并不那么容易能找到3种方法。我觉得,如果你能在10分钟内找出这三种方法,说明你真的很聪明,而且反应很快。当然,15分钟内也不赖。不过,你要是30分钟内找不到三种方法,当然,不说明你笨了,最多就是你的反应还不够快。嘿嘿。就当是玩玩吧。

下面是我的答案:


 
//第一种解法:在for循环中给n加一个负号
for(int i = 0; i < -n; i--)
//第二种解法:把 n 初始化成 -20
int n = -20;
//第三种解法:把for循环中的 i 初始化成40
for(int i = 40; i < n; i--)

不过,我要告诉你,以上这些答案都不对(我就知道你会偷看答案的),不过,顺着这些思路走很接近了。呵呵。

下面是正确答案——



//第一种解法:在for循环中给 i 加一个负号
for(int i = 0; -i < n; i--)

//第二种解法:在for循环中把 i-- 变成 n--
for(int i = 0; i < n; n--)

//第三种解法:把for循环中的 < 变成 +
for(int i = 0; i + n; i--)

其它相关的变种题如下:

  • 通过修改、增加一个字符,让其输出21个减号
  • 通过修改、增加一个字符,让其只输出1个减号
  • 通过修改、增加一个字符,让其不输出减号

(全文完)