工作笔试(五)x&(x-1)

求下面函数的返回值(微软)
-------------------------------------
int func(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

int func(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) == 优先级高于 &

工作笔试(二) Count the number of bits set in a 32-bit word

Answer to Ex2: Count the number of bits set in a 32-bit word

C code:

int counter=0;

for (i=0; i<32; i++) {
bit = input & (1< if (bit==1)
counter++;
}

MIPS code:
Assume: input is in $t0, counter is in $t1, bit is in $t2, i is in $t3

Addi $t5, $zero, 1 ;$t5 holds constant 1
Addi $t3, $zero, 32 ;$t3 is the loop index

Loop Sllv $t4, $t5, $t3 ;$t4=1< And $t2, $t0, $t4 ;$t2=input & (1< Beq $t2, $zero, Label ;is $t2 0?
Addi $t1, $t1, 1 ;$t1++
Label addi $t3, $t3, -1 ;decrement $t3
Bne $t3, $zero, Loop

工作笔试(一) strstr()的简单实现

strstr(s1,s2)是一个经常用的函数，他的作用就是在字符串s1中寻找字符串s2如果找到了就返回指针，否则返回NULL。下面是这个函数的一个简单实现：

static const char* _strstr(const char* s1, const char* s2)
{
  assert(s2 && s1);
  if(S1 == '\0') return NULL;

  const char* p=s1, *r=s2;
  while(*p!='\0')
  {
       while(*p++==*r++ && *p!='\0' && *r!='\0');
       if(*r=='\0')
            return s1;
       if(*p=='\0')
            return NULL;
        r=s2;
        p=++s1;
  }
  return NULL;
}