给定a和b两个整数如何不使用比较和判断操作来实现输出其最大值?
这里可以学习几个有趣的函数:
1 获取一个数的正或负符号
2 反转一个符号
这里是通过符号的判断来巧妙地实现的。
基本思路:
符号位正,用1表示,符号是负用0表示。
有四种情况:
1 a b同号, a正,b负,那么最大值肯定是a,只要a乘以自己的符号1,b乘以自己的符号0,得出的就是最大值
2 a b同号, 也一样道理
3 a b异号, k = a-b的符号,a*k+b*k如果a大,那么k为1,式子等于a,如果b大,那么k为0,式子等于b。返回a*k + b*k就是其最大值了
4 a b异号, 一样道理
为什么要分四种情况呢?因为要考虑a b异号的时候a-b有可能溢出,这里最巧妙的就是不通过判断实现这四种情况了。
这个直接看程序,然后跟着程序走几遍,应该就没问题了。
分四种情况走一走,看看下面程序中的k值如何取得。
#include<iostream>
#include<vector>
using namespace std;
int flipSign(int a)
{
return a^1;
}
int getSign(int a)
{
//we need &0x1, ortherwise we won't be able to flip minus.
//if positive, return 1, minus, return 0
return flipSign((a>>31)&0x1);
}
int maxWithComp(int a, int b)
{
int c = a-b;
int sa = getSign(a);
int sb = getSign(b);
int sc = getSign(c);
//if a b are different sign, use_sign_of_a = 1; use_sign_of_c = 0; otherwise the other way around
int use_sign_of_a = sa^sb;
int use_sign_of_c = flipSign(sa^sb);
//if a is positive, and a b are the same sign, use_sign_of_a is 0; k the same sign as sc
//if a is positive, and a b are the different sign, k is positive, the same sign as a
//if a is negative, and a b are the same sign, use_sign_of_a is 0; k the same sign as sc
//if a is negative, and a b are the defferent sign, k is negative, the same sign as a
int k = use_sign_of_a * sa + use_sign_of_c * sc;
int q = flipSign(k);
return a*k + b*q;
}
int main()
{
cout<<maxWithComp(8,5)<<endl;
cout<<maxWithComp(-8,5)<<endl;
cout<<maxWithComp(2, 9)<<endl;
cout<<maxWithComp(2,-9)<<endl;
cout<<maxWithComp(-29, -200)<<endl;
system("pause");
return 0;
}
reference:
Cracking the coding interview
分享到:
相关推荐
主要介绍了JavaScript遍历查找数组中最大值与最小值的方法,结合实例形式分析了javascript基于数组遍历、判断实现最大值与最小值计算的相关操作技巧,需要的朋友可以参考下
js代码-查找table表格数据中每一列的最大值与最小值
C语言程序设计-编写程序。...⑴求出这8个数据的和、最大值、最小值及平均值。 ⑵求这8个数据的正数之和、负数之和(或正数与负数的个数); ⑶求这8个数据的奇数之和、偶数之和(或奇数与偶数的个数)。
while(low){ if(x==arr[mid]){ return mid; } else if(mid>0&&x[mid]){... else if(mid){//若前面没有判断,则当要查找数超过arr数组中最大值时出现死循环。 low=mid+1; mid=(low+high)/2; }
2、 能够人工输入或随机产生一个长度为 n 的整数数组,要求数组任意两个元素都互不相同;...7、 给定先升后降(或先降后升)数组,使用二分检索思路查找该数组的最大值(或最小值),并统计关键字比较的次数。
第九章 查找习题 9.1若简单顺序查找算法所要查找的元素的下标从0开始,因而不能用监视哨,故查找 失败时要返回-1。试设计相应的算法。 9.2对有序数据表(5,7,9,12,15,18,20,22,25,30,100),按二分查找方法模拟查找 ...
本文实例讲述了PHP获取数组最大值下标的方法。... 您可能感兴趣的文章:PHP判断一个数组是另一个数组子集的方法详解PHP查找数值数组中不重复最大和最小的10个数的方法php获取数组中键值最大数组项的索引值php求正负
50052 使用函数找最大值 49 50062 使用函数输出指定范围内的 Fibonacci 数 50 50063 使用函数找出指定范围内的完数 51 第8周(M8) 52 40013 求奇数和 52 40062 求x+x*x/2!+x*x*x/3!+x*x*x*x/4!+……的值 53 ...
还是只是记录下来相关位置——这是我底下未完成版本1想到的思路——用一个count[sizeof(A)]数组记录下A每个位置作为起点所能和B达到的最大重合,最后判断查找数组中最大值,此时目标子字符串的起点下标(i)和 i ...
熵,欧几里得距离,欧几里得最大公约数,欧拉方法,改进欧拉方法,欧拉函数,扩展欧几里得算法,阶乘,因数,费马小定理,斐波那契数列,查找最大值,递归查找最大值,查找最小值,递归查找最小值,下取整,伽马函数...
能使用二分法查找的线性表必须满足用顺序存储结构和线性表是有序表两个条件。 “有序”是特指元素按非递减排列,即从小到大排列,但允许相邻元素相等。下一节排序中,有序的含义也是如此。 对于长度为n的有序线性表...
去掉其中两个最大值和两个最小值的公式 去一行最高分最低分求平均值 在9个数值中去掉最高与最低然后求平均值 求最大值(n列) 如何实现求平均值时只对不等于零的数求均值? 得到单元格编号组中最大的数或最小的数 ...
去掉其中两个最大值和两个最小值的公式 去一行最高分最低分求平均值 在9个数值中去掉最高与最低然后求平均值 求最大值(n列) 如何实现求平均值时只对不等于零的数求均值? 得到单元格编号组中最大的数或最小的数 ...
查找数组中的最大元素 查找数组中的最小元素 对数组进行排序 计算数组的中位数 计算数组的众数 计算数组的平均值 判断数组是否为严格递增 计算二维数组中所有元素的和 旋转二维数组90度 寻找目标数组是否为原数组的...
技巧154查找最大、最小值379 技巧155不重复值的录入381 技巧156获得当月的最后一天383 技巧157四舍五入运算384 157-1极小值修正法384 157-2调用工作表函数法385 技巧158使用字符串函数385 技巧159使用日期函数387 ...
技巧154 查找最大、最小值 381 技巧155 不重复值的录入 383 技巧156 获得当月的最后一天 385 技巧157 四舍五入运算 386 157-1 极小值修正法 386 157-2 调用工作表函数法 387 技巧158 使用字符串函数 387 技巧159 ...
删除重复记录的方法原理:在Oracle中,每一条记录都有一个rowid,rowid在整个数据库中是唯一的,rowid确定了每条记录是在Oracle中的哪一个数据...重复记录判断的标准是:C1,C10和C20这三列的值都相同才算是重复记录。
所谓鞍点是指矩阵中的某个元素在其所在的行是最小的,同时在其所在列是最大的。选择合适的矩阵存储方式。以一个4行5列的矩阵为例,从键盘人已输入20个数据给矩阵赋值,然后判断其中是否存在鞍点。如果存在鞍点,输出...