剑指offer系列之四十七:不用加减乘除做加法

题目描述

写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号

既然不能使用加减乘除,那么只剩下位运算和逻辑运算了。采用位运算的思路分为三步走:第一步,不进位对两个做异或运算(因为不考虑进位,1与1,0与0的异或运算的结果刚好是两者相加的结果);第二步,通过与运算得到两个数的进位值,因为只有1与1进行与运算的时候才会产生进位,所以产生的进位可以看成是两者先进行与运算再左移一位;第三步,把前两步的结果做与运算得到最后的结果。个人觉得这种思路是在是太赞了。OK,事就成了。下面是这种思路的实现代码(已被牛客AC):

package com.rhwayfun.offer;

/**
 * 不使用操作运算符
 *
 * @author Administrator
 *
 */
public class CalcSumNoOperation {

    public int Add(int num1, int num2) {
        int sum = 0;
        int carray = 0;
        while(num2 != 0){
            sum = num1 ^ num2;
            carray = (num1 & num2) << 1;

            num1 = sum;
            num2 = carray;
        }
        return num1;
    }

    public static void main(String[] args) {
        int a = new CalcSumNoOperation().Add(2, 9);
        System.out.println(a);
    }
}
时间: 2024-10-01 10:56:23

剑指offer系列之四十七:不用加减乘除做加法的相关文章

剑指offer系列之四十二:约瑟夫环问题

题目描述 每年六一儿童节,NowCoder都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此.HF作为NowCoder的资深元老,自然也准备了一些小游戏.其中,有个游戏是这样的:首先,让小朋友们围成一个大圈.然后,他随机指定一个数m,让编号为0的小朋友开始报数.每次喊到m的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0-m-1报数-.这样下去-.直到剩下最后一个小朋友,可以不用表演,并且拿到NowCoder名贵的"名侦探柯南"

剑指offer系列之十七:二叉树的镜像

题目描述 操作给定的二叉树,将其变换为源二叉树的镜像. 输入描述: 二叉树的镜像定义:源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5 仔细观察原二叉树与镜像二叉树,可以发现镜像二叉树实际上就是把每个节点的左右孩子结点进行了交换,比如在遍历到8这个节点时候,首先交换其左右孩子6和10,其对应的子树也应该进行交换.所以我们可以采用前序遍历的方法进行操作,每当遇到一个结点的时候,首先判断其是否有左右孩子(有其中之一即

剑指offer系列之四十八:把字符串转成整数

题目描述 将一个字符串转换成一个整数,要求不能使用字符串转换整数的库函数 这里的关键是要对输入的字符串进行全面的考虑.包括字符串是否有效的判断.是否是负数以及字符串表示的整数是否越界等问题.对于字符串有效性的判断主要是null以及空串的判定:负数之所以需要判断是因为在计算的时候是有用的:而是否越界的问题也是需要考虑的.因为一个越界的数是不可能计算出来的,那么这时候可以简单返回一个0,表示越界的数.这三点都考虑之后,整体代码的健壮性就比较好了.下面是这种思路的实现代码(已被牛客AC),详细的已经在

剑指offer系列之四十六:求1到n的和

题目描述 求1+2+3+-+n,要求不能使用乘除法.for.while.if.else.switch.case等关键字及条件判断语句(A?B:C). 如果不能使用上面的操作,那么只能使用递归操作了.使用递归操作的思路是让函数不断调用自己,每调用一次值就减少1,这样完成了递归操作.还有一个问题是如何实现n范围的判断呢?注意到递归调用的n的值最小是1,所以可以通过逻辑与运算,判断是否递归到1.如果递归调用到1,那么递归就结束,并返回最后的结果.下面是这样思路的实现代码(已被牛客AC): packag

剑指offer系列之四十一:和为S的两个数字且乘积最小

题目描述 输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的. 输出描述: 对应每个测试案例,输出两个数,小的先输出. 有了上一题的基础,解决这题应该不难,思路与上一题差不多,不过这里只需要要求两个数字即可.所以可以设定两个指针,第一个指针指向数组的第一个元素,第二个指针指向最后一个元素,不断改变第一个指针的位置就可以确定和为S的两个数字.这里还有一个要求是这两个数字的乘积最小,实际上由于数组是递增排序的,所以第一个找到

剑指offer系列之四:重建二叉树

题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字.例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回. 在完成代码之前,我自己分析了一下如何根据前序遍历和中序遍历的结果构建一棵二叉树.首先,根据二叉树遍历的性质,由前序遍历的结果序列可知该二叉树的根节点是1,在根据中序遍历的结果可是根节点1的左子树包含的结点是4.7.2,右子树包含的节点是5.3.8.6.

剑指offer系列之四十:和为S的连续正数序列

题目描述 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100.但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数).没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22.现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck! 输出描述: 输出所有和为S的连续正数序列.序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序 此题的思路是:设定两个指针,一个指向第一个

剑指offer系列之四十九:数组中重复的数字

题目描述 在一个长度为n的数组里的所有数字都在0到n-1的范围内. 数组中某些数字是重复的,但不知道有几个数字是重复的.也不知道每个数字重复几次.请找出数组中任意一个重复的数字. 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3. 此题的思路还是比较简单的,与之前找出只出现一次的数字的题目有些类似,基本思路还是创建一个Map容器,key是出现的数字,value则是该数字出现的次数.在遍历数组的过程中,只要容器中已经出现了该数字,那么就直接返回给数组,

剑指offer系列之四十四:翻转单词顺序

题目描述 牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上.同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思.例如,"student. a am I".后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是"I am a student.".Cat对一一的翻转这些单词顺序可不在行,你能帮助他么? 可以发现,要对一个句子进行翻转,可以先对整个句子进行翻转,之后再对每个单词进行翻转.而不论是返