每日一题 (不用加减乘除做加法,找到数组中消失的数字)

简介: 每日一题 (不用加减乘除做加法,找到数组中消失的数字)

不用加减乘除做加法_牛客题霸_牛客网 (nowcoder.com)

可以使用位运算符实现两个整数的加法:

在二进制加法中,我们通常使用“逐位相加”的方法来模拟常规加法的过程。当两个数字进行加法运算时,从最低位(通常是右侧)开始相加,然后考虑进位。如果相加的结果产生进位,那么这个进位会被带到下一位的加法中。

while (b != 0) 循环是为了确保所有的位都被正确地相加,并处理了所有可能的进位。这里 b 实际上充当了一个“进位标志”的角色。只要 b 不为0,说明还有进位需要处理,所以循环会继续执行。

具体来说:

  1. b 为0时,意味着没有进位,加法运算已经完成。
  2. b 不为0时,表示还有进位需要加到下一位上。这时,通过 a = a ^ b; 计算当前位(不考虑进位的和),然后通过 b = carry << 1; 将进位左移一位(即考虑到下一位的加法中)。

这种算法通常被称为“无进位加法”或“二进制加法”,它模仿了人类手动进行二进制数加法的过程。通过不断迭代,直到没有进位为止(即 b 为0),最终得到两个二进制数的和。

简而言之,while (b != 0) 循环确保了所有位都被正确相加,并且处理了所有可能的进位,直到得到一个最终的和,其中没有进一步的进位需要处理。

在二进制加法中,b = carry << 1; 这一步是将进位(carry)左移一位。这模拟了在传统的十进制加法中,当两个数字相加的和超过9时,我们会进一位到更高的数位。在二进制中,这个概念类似,只是数字变成了2而不是10。

让我们分解这一步:

  1. 进位(carry: 在二进制加法中,carry 变量存储了上一轮加法运算产生的进位。这个进位是那些在两个相加数字的对应位上都是1的位产生的。在二进制中,1 + 1 = 10,所以产生了一个进位(1)和一个输出位(0)。
  2. 左移一位(<< 1: 在计算机中,左移操作等同于乘以2。因此,将进位值左移一位实际上是将它乘以2。在二进制加法中,这表示将进位传递到更高的位。例如,如果在最低位(第0位)有一个进位,左移一位后,这个进位就会出现在下一位(第1位)。
  3. 更新 b: b 变量在算法中扮演着双重角色。在最开始的迭代中,它是第二个加数。但在后续的迭代中,它存储了从上一次迭代传递下来的进位。因此,b = carry << 1; 更新了 b 的值,以便在下一次循环迭代中处理这个进位。

这个过程重复进行,直到没有进位(b == 0)为止。每次迭代都处理一对位,并可能产生一个新的进位,这个进位在下一次迭代中被处理。最终,当没有更多的进位需要处理时,算法完成,a 变量中存储的就是两个原始数字的和。

总结来说,b = carry << 1; 这一步是二进制加法中的关键部分,它负责将进位传递到更高的位,并准备在下一次循环迭代中处理这个进位。

#include <stdio.h>  
  
int addWithoutArithmetic(int a, int b) {  
    while (b != 0) {  
        int carry = a & b;  //这步操作找出两个数在相同位置都为1的位,这些位将在加法中产生进位
        a = a ^ b;  //得到没有考虑进位的加法结果。这步操作找出两个数在不同位置为1的位,这些位将在加法中产生1
        b = carry << 1;  
    }  
    return a;  
}  
  
int main() {  
    int num1 = 5;  
    int num2 = 3;  
    int sum = addWithoutArithmetic(num1, num2);  
    printf("The sum of %d and %d is %d\n", num1, num2, sum);  
    return 0;  
}

448. 找到所有数组中消失的数字 - 力扣(LeetCode)

代码使用了一种巧妙的方法,即利用数组元素的正负性标记其是否出现过,从而找出缺失的数字 。

#include <stdio.h>  
#include <stdlib.h>  
  
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize)
//接受一个整数数组nums、数组的大小numsSize,以及一个用于返回结果数组大小的指针returnSize{  
    // 遍历数组,将元素对应的索引位置上的元素取负值  
    for (int i = 0; i < numsSize; i++) {  //遍历数组nums,将元素对应的索引位置上的元素取负值。因为数组中的元素范围是1到n,所以我们用abs(nums[i]) - 1来得到对应的索引(减1是因为数组索引从0开始)。如果索引i上的元素是正数,就将其取负值,表示这个数字出现过
        int index = abs(nums[i]) - 1; // 将元素值转换为索引,因为元素值在1到n之间  
        if (nums[index] > 0) { // 确保不会对一个负数取反  
            nums[index] = -nums[index];  
        }  
    }  
  
    // 找出那些仍然为正数的索引,这些索引对应的数字就是缺失的数字  
    int* result = (int*)malloc(numsSize * sizeof(int));  
    int count = 0;  
    for (int i = 0; i < numsSize; i++) {  //再次遍历数组nums,找出那些仍然为正数的索引。这些索引对应的数字就是缺失的数字。对于每个正数索引i,将i + 1(因为缺失的数字范围也是1到n)添加到结果数组result中,并增加计数器count
        if (nums[i] > 0) {  
            result[count++] = i + 1; // 将索引转换为缺失的数字,并计数  
        }  
    }  
  
    // 设置返回数组的大小  
    *returnSize = count;  
  
    return result;  
}  
  
int main() {  
    int nums[] = {4, 3, 2, 7, 8, 2, 3, 1};  
    int numsSize = sizeof(nums) / sizeof(nums[0]);  
    int returnSize;  
    int* result = findDisappearedNumbers(nums, numsSize, &returnSize);  
  
    printf("The missing numbers are: ");  
    for (int i = 0; i < returnSize; i++) {  
        printf("%d ", result[i]);  
    }  
    printf("\n");  
  
    // 释放结果数组的空间  
    free(result);  
  
    return 0;  
}
相关文章
|
存储 前端开发 Java
Python 教程之控制流(9)Python 中的 Switch Case(替换)
Python 教程之控制流(9)Python 中的 Switch Case(替换)
343 0
|
PHP 数据库 数据安全/隐私保护
|
存储 安全 固态存储
删除的文件还能回来吗?当然可以!教你如何恢复
误删文件不必慌,恢复机会仍存在!删除的文件常被标记而非立即清除,故在新数据覆盖前,文件恢复是可能的。SSD例外,因其TRIM功能即时擦除。恢复步骤:检查回收站,利用系统恢复功能,或专业软件如DiskGenius扫描硬盘。及时行动,避免数据覆盖至关重要。预防最佳:定期备份,谨慎操作,启用安全防护,确保数据安全无忧。记得,预防优于事后恢复!🚀✨ (239 characters)
删除的文件还能回来吗?当然可以!教你如何恢复
|
SQL 关系型数据库 MySQL
AnalyticDB MySQL
【8月更文挑战第30天】AnalyticDB MySQL
291 4
|
7月前
|
传感器 程序员 Go
一文彻底搞清楚常见的IC封装
本文介绍了常见的IC封装类型,包括DIP、SOP、QFP、BGA、CSP等,详细解释了它们的特点、应用及选型参考,帮助读者理解封装技术的发展趋势与核心功能。
1675 0
一文彻底搞清楚常见的IC封装
|
6月前
|
边缘计算 安全 数据安全/隐私保护
一个pcdn产品体验
闲置宽带还能赚钱?听起来是不是很神奇?作为一名普通打工人,我最近入手了负三云这个“小盒子”,体验后直呼真香!只需将其连接路由器,就能利用闲置带宽获取收益。我家100M宽带,每天稳定收入5-8元,一个月轻松赚200+,完全覆盖网费。安装简单、不影响网速,功耗低且安全可靠。如果你也想尝试边缘计算,低成本的负三云绝对值得一试!
2403 0
|
消息中间件
【RabbitMQ七】——RabbitMQ发布确认模式(Publisher Confirms)
【RabbitMQ七】——RabbitMQ发布确认模式(Publisher Confirms)
692 0
|
Prometheus 监控 Cloud Native
应用程序部署
应用程序部署
305 3
|
10月前
|
存储 缓存 NoSQL
一篇搞懂!Java对象序列化与反序列化的底层逻辑
本文介绍了Java中的序列化与反序列化,包括基本概念、应用场景、实现方式及注意事项。序列化是将对象转换为字节流,便于存储和传输;反序列化则是将字节流还原为对象。文中详细讲解了实现序列化的步骤,以及常见的反序列化失败原因和最佳实践。通过实例和代码示例,帮助读者更好地理解和应用这一重要技术。
463 0
|
前端开发 JavaScript UED
element-ui 表格数据究竟隐藏着怎样的神秘样式与格式化技巧?快来揭开谜底!
【8月更文挑战第22天】《element-ui 表格数据样式及格式化案例》展示了如何利用 element-ui 的表格组件实现美观且易读的数据展示。通过简单配置,可以自定义表格样式,如边框、背景色等,并通过 formatter 实现数据格式化,例如将成绩保留一位小数。此外,还能依据条件设置行样式,如成绩达优则高亮显示,从而增强用户体验和数据可读性。
233 1