练习题(2)
Suzhou 57 0

练习题(2) ::: tip 内存中存放的是补码,即计算一个数的补码的二进制序列中1的数量。

十进制的每一位通过模10除10得到,同样二进制可以通过模2除2得到。 ::: 源码得到反码时,符号位不变,其他位按位取反,反码+1得到补码。 正数的原码反码补码相同。

int count_bit_one(unsigned int a)
{
    int count = 0;
    while (a)
    {
        if (a % 2 == 1)
        {
            count++;
        }
        a = a / 2;
    }
    return count;
}

int main()
{
    int a = 0;
    scanf("%d", &a);
    int count = count_bit_one(a);
    printf("%d", count);
    return 0;
}
-1
32

上述代码中使用unsigned将负数强制转换成无符号数。 负数在内存中的补码的二进制位的1的个数计算,可以将负数的补码的符号位当成有效位,如-1的补码,变为无符号数后再模2除2。


另一种做法是将二进制数的每一位取出,如果是1则计数器count++,直到二进制数的最后一位。

int count_bit_one(int a)
{
    int count = 0;
    int m = 0;
    while (m < 32)
    {
        a >> m;
        if (a & 1 == 1)
        {
            count++;
        }
        m++;
    }
    return count;
}

int main()
{
    int a = 0;
    scanf("%d", &a);
    int count = count_bit_one(a);
    printf("%d", count);
    return 0;
}
-1
32

按位与时两个数字都为1才为1,有一个0即为0。一个二进制数和1按位与时,只有最后一位数字为1,按位与的结果才为1。将该二进制数每次向后移动一位,和1按位与,直到该数的32位全部和1进行过按位与,统计按位与的结果中1的数量。


代码的精简写法:

int count_bit_one(int a)
{
    int count = 0;
    while (a)
    {
        a = a & (a - 1);
        count++;
    }
    return count;
}

int main()
{
    int a = 0;
    scanf("%d", &a);
    int count = count_bit_one(a);
    printf("%d", count);
    return 0;
}

::: tip a = a & (a - 1)的写法,是将a的二进制数中每次去掉一个1。 如a=13(1011),a&(a-1)=1101&1100=1100,1100赋给a,相比于原来a的值1101,去掉了最后面的1。1100&1011=1000,1000赋给a,相比于原来a的值1100,再去掉最后的一个1。直到a的值变为0000,离开while循环,返回计数器。 ::: 练习题(2) 上述题目思路可以将二进制数的每一位拿出来单独比较,但是代码效率不高。 可以从异或入手:

int count_diff_bit(m, n)
{
    int tmp = m ^ n;
    int count = 0;
    while (tmp)
    {
        tmp = tmp & (tmp - 1);
        count++;
    }
}

int main()
{
    int m, n;
    scanf("%d %d",&m,&n);
    int count = count_diff_bit(m, n);
    printf("%d", count);
    return 0;
}
1999 2299
7

上述代码的思路为:将两个数异或操作,在异或操作结果中数出数字1的个数。 ::: tip 异或操作符:对应二进制相同为0,相异为1。 ::: 练习题(2)

void Print(int a)
{
    int i = 0;  //向右移动的位置,从右往左0、2、4...
    printf("奇数位是:");  //从右往左的1、3、5...
    for(i = 30;i >= 0;i -= 2)  //最后一位奇数无需移动(移动0位),即i最小为0
    //打印时候从左往右,从右往左计数第31位是最后一个奇数位,需要向右移动30位才能到达最后一位1的位置
    {
        printf("%d ", (a>>i)&1);
    }
    printf("\n");
    printf("偶数位是:");  //从右往左的2、4、6...
    for (i = 31; i >= 1; i -= 2)  //最后一位偶数需要向右移动1位,即i最小为1
        //打印时候从左往右,从右往左计数第32位是最后一个偶数位,需要向右移动31位才能到达最后一位1的位置
    {
        printf("%d ", (a >> i) & 1);
    }
}

int main()
{
    int a = 0;
    scanf("%d",&a);
    int m = 0;
    Print(a);
    return 0;
}
150
奇数位是:0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
偶数位是:0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1

练习题(2) 上述代码反复调用得到Fun函数中n=5,返回2,即Fun函数的结果是2,一级一级×2返回,直到最后一层返回16。 练习题(2)

void print(n)
{
    int i = 0;
    for (i = 0; i <= n; i++)
    {
        int j = 0;
        for (j = 0; j <= i; j++)
        {
            printf("%d*%d=%-3d ",i,j,i*j);
        }
        printf("\n");
    }
}

int main()
{
    int n = 0;
    scanf("%d",&n);
    print(n);
    return 0;
}
9
0*0=0
1*0=0   1*1=1
2*0=0   2*1=2   2*2=4
3*0=0   3*1=3   3*2=6   3*3=9
4*0=0   4*1=4   4*2=8   4*3=12  4*4=16
5*0=0   5*1=5   5*2=10  5*3=15  5*4=20  5*5=25
6*0=0   6*1=6   6*2=12  6*3=18  6*4=24  6*5=30  6*6=36
7*0=0   7*1=7   7*2=14  7*3=21  7*4=28  7*5=35  7*6=42  7*7=49
8*0=0   8*1=8   8*2=16  8*3=24  8*4=32  8*5=40  8*6=48  8*7=56  8*8=64
9*0=0   9*1=9   9*2=18  9*3=27  9*4=36  9*5=45  9*6=54  9*7=63  9*8=72  9*9=81

练习题(2) 使用C语言库函数的解法(不符合题目要求):

#include <string.h>
void reverse(char arr[])
{
    int left = 0;
    int right = strlen(arr) - 1;
    int tmp = 0;
    while (left < right)
    {
        tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        left++;
        right--;
    }
}

int main()
{
    char arr[] = "abcdef";
    reverse(arr);
    printf("%s\n",arr);
    return 0;
}
fedcba

使用递归方式(使用递归实现strlen):

int my_strlen(char* str)
{
    int count = 0;
    while (*str != '\0')
    {
        count++;
        str ++;
    }
    return count;
}

void reverse(char arr[])
{
    char tmp = arr[0];
    int len = my_strlen(arr);
    arr[0] = arr[len - 1];
    arr[len - 1] = '\0';
    if (my_strlen(arr + 1) > 1)  //arr是指针,函数中char arr[]可以写成char* arr
    {
        reverse(arr + 1);
    }
    arr[len - 1] = tmp;
}

int main()
{
    char arr[] = "abcdef";
    reverse(arr);
    printf("%s\n",arr);
    return 0;
}

::: tip 代码思路: 在字符串abcdef\0中 1.将a暂存在临时变量。 第14行代码 2.f放在a的位置,原来f的位置放\0。 第16、17行代码 3.bcde逆序。 第20行代码 4.临时变量存储的a放在原来f的位置。 第22行代码 第一轮交换a和f结束,递归此操作。 ::: 上述代码中18行递归的条件: 交换首尾两个元素的位置后,中间需要逆序的字符串大于1。 在15到17行代码已经把字符串最外层的两个元素进行了交换,第18行代码判断时应该从下标为1的元素开始计算需要逆序的字符串的长度,即len(arr+1),len的计算使用的是my_string函数,即my_string(arr+1)。

练习题(2) 循环实现:

void DigisSum(unsigned int num)
{
    int sum = 0;
    while (a > 0)
    {
        sum += num % 10;
        num = num / 10;
    }
    printf("%d", sum);
}

int main()
{
    int num = 0;
    scanf("%d", &num);
    DigisSum(num);
    return 0;
}

递归实现:

//1729 
//DigisSum(172)+1729%10
//DigisSum(17)+(1729/10)%10+1729%10
//DigisSum(1)+((1729/10)/10)%10+(1729/10)%10+1729%10
//num<10时直接相加。即1+7+2+9
int DigitSum(unsigned int num)
{
    if (num >= 10)
    {
        return DigitSum(num / 10) + num % 10;
    }
    else
    {
        return num;
    }
}

int main()
{
    int num = 0;
    scanf("%d", &num);
    int ret = DigitSum(num);
    printf("%d",ret);
    return 0;
}

练习题(2)

double Pow(int n, int k)
{
    //n^k = n*n^(k-1)
    if (k > 0)
    {
        return n * Pow(n, k - 1);
    }
    else if (k == 0)
    {
        return 1;
    }
    else
    {
        return (1.0 / Pow(n, -k));  //一个数的负次方即为这个数的正次方的倒数
    }
}

int main()
{
    int n = 0;
    int k = 0;
    scanf("%d %d",&n,&k);
    double ret = Pow(n, k);
    printf("ret = %lf\n", ret);
    return 0;
}

::: tip n^k = n*n^(k-1) :::

评论区

索引目录