【答案贴】看到一个面试题，大家来讨论下！解决方案

【答案贴】看到一个面试题，大家来讨论下！
原帖请见：看到一个面试题，大家来讨论下！
因为那个帖子太长了，我结了。这个帖子里主要贴几个典型的解法。

我认为比较好的解法（在Blog里也写了这个方法：不用比较运算符，判断int型的a，b两数的大小）

Java code

public class Bigger {    public static void main(String args[]){        int a = -2147483648;        int b = 2147483647;                String[] strArray = {"a>=b", "a<b"};                        int i = (int)((long)a-(long)b >>> 63);                System.out.println(strArray[i]);    }}

然后我在回帖中看到了几个很典型的方法（注意：不用比较运算符，不用类库方法。）

Java code

System.out.println(a-b);  //无语，那还不如int a=1; int b=2;直接拿眼睛看算了。

Java code

if(!(a-b)) {     if(abs(a-b)-(a-b))      {         return "a < b";     }     else     {         return "a > b";     } } else {     return "a = b"; }//方法很好，数学里整数能到无穷大，但是计算机里不行啊。

Java code

public String compare(Integer x,Integer y){   String [] buf={"=>"," <"};   int id1=(x-y)>>>31;    System.out.println(id1);   return buf[id1]; }//也是没有考虑越界问题

还有些是用接口实现的，有点复杂了。有很多人会问，搞这个东西有什么实际的用途吗？是，确实没什么用，不如直接比较。但是有时候我们中国人就是被这种“有没有用”的功利主义给害了。研究数学，物理和化学有用吗？是没有直接的作用，但是你看看为什么美国，日本，德国的工业和高科技产业如此发达，还不是靠基础科学的投入吗？Google为了提高搜索算法的效率，也是投入巨资。不是什么东西有用没用就能简单的决定你去不去做一件事情，因为你不去做一件事情，就无法知道你在做这件事情的过程中会有什么收获。有一句话说的好：人生是曲折的，但生活是精彩的。



[解决办法]
学习了
[解决办法]
“不是什么东西有用没用就能简单的决定你去不去做一件事情，因为你不去做一件事情，就无法知道你在做这件事情的过程中会有什么收获。”嗯，很同意楼主的观点。我们现在很多同学都抱怨基础课没用，都跑去学流行的语言或快见效果的所谓“新技术”，从而忽视了数据结构与算法、编译原理等基础课的学习。
[解决办法]
不错，算法的效率确实重要！
[解决办法]

引用楼主 justinavril 的帖子:

还有些是用接口实现的，有点复杂了。有很多人会问，搞这个东西有什么实际的用途吗？是，确实没什么用，不如直接比较。但是有时候我们中国人就是被这种“有没有用”的功利主义给害了。研究数学，物理和化学有用吗？是没有直接的作用，但是你看看为什么美国，日本，德国的工业和高科技产业如此发达，还不是靠基础科学的投入吗？Google为了提高搜索算法的效率，也是投入巨资。不是什么东西有用没用就能简单的决定你去不去做一件事情，因为你不去做一件事情，就无法知道你在做这件事情的过程中会有什么收获。有一句话说的好：人生是曲折的，但生活是精彩的。

[解决办法]
好贴！！！！！！！！！
[解决办法]
支持楼主~!
[解决办法]
借鉴楼主的精彩答案，我这里是一个完整版：

Java code

import java.util.Random;/** * 不通过比较运算和类库，比较两个 integer 大小 */public class SimpleCompare {    public static void main(String[] args) {        Random r = new Random();        int a = r.nextInt(), b = r.nextInt();        // int a = 33, b = 33;        String[] results = {"a < b", "a == b", "a > b"};        int sum = 1;        sum = sum - (int)((long)(a - b) >>> 63);        sum = sum + (int)((long)(b - a) >>> 63);        System.out.println(a + ", " + b + ": " + results[sum]);    }}
[解决办法]
up!!
[解决办法]
好帖子阿..又学习了.!UP
------解决方案-------------------- 
 
学习了
[解决办法]
学习了，以前一直不太注意这些东西
[解决办法]
探讨

借鉴楼主的精彩答案，我这里是一个完整版： 

Java codeimport java.util.Random;

/**
 * 不通过比较运算和类库，比较两个 integer 大小
 */
public class SimpleCompare {

    public static void main(String[] args) {
        Random r = new Random();
        int a = r.nextInt(), b = r.nextInt();
        // int a = 33, b = 33;

        String[] results = {"a < b", "a == b", "a > b"};

     …

[解决办法]
这种比较应该是输出更大的那个数字，而不是输出比较结果啊。
[解决办法]
学习
[解决办法]
学习了,楼主顺便说下第一个算法是啥意思?
[解决办法]
学习了
[解决办法]
支持楼主！
[解决办法]

Java code
    if( (abs(a-b)+abs(a-b)) /2 == a)      {         System.out.println("a > b");     }     else     {         System.out.println("a < b");    }
[解决办法]
看看，学习啦
[解决办法]
学习
[解决办法]
我博客里已经写了答案！

不用比较运算符，判断int型的a，b两数的大小,考虑溢出问题
[解决办法]
也许楼主说的不错。
有用没用也许是我们的想象力太差。
[解决办法]
不是什么东西有用没用就能简单的决定你去不去做一件事情，因为你不去做一件事情，就无法知道你在做这件事情的过程中会有什么收获。有一句话说的好：人生是曲折的，但生活是精彩的。  

学习咯。

[解决办法]
Java code
public class Test5 {    public static void main(String[] args) {        int a = -2147483648;        int b = 2147483647;        System.out.println(max(a, b));    }    public static int max(int a, int b) {        int k = (~(a ^ b) >>> 31) * (a - b) >>> 31;        k += ((a ^ b) >>> 31) * (a >>> 31);        return b * k + a * (k ^ 1);    }}
[解决办法]
也写一个玩玩：
public class Compare {
private static final boolean signToBool[] = { true, false };

private static final boolean getSignOfInteger(int integer) {
return signToBool[integer >>> 31];
}

public static boolean compareInteger(int int1, int int2) {
boolean signOfInt1 = getSignOfInteger(int1);
boolean signOfInt2 = getSignOfInteger(int2);
boolean signInt1MinusInt2 = getSignOfInteger(int1 - int2);
return (!(signOfInt1 ^ signOfInt2) && signInt1MinusInt2)
|| ((signOfInt1 ^ signOfInt2) && signOfInt1);
}
}
测试代码：
import java.util.Calendar;
import java.util.Random;

import junit.framework.TestCase;

public class CompareTest extends TestCase {

public void testCompareWithSimpleIntegers() {
assertTrue(Compare.compareInteger(1, 1));
assertTrue(Compare.compareInteger(0, 0));
assertTrue(Compare.compareInteger(-1, -1));

assertTrue(Compare.compareInteger(1, 0)); 
 
assertTrue(Compare.compareInteger(0, -1));
assertTrue(Compare.compareInteger(2, 1));
assertTrue(Compare.compareInteger(1, -1));
assertTrue(Compare.compareInteger(-1, -2));

assertFalse(Compare.compareInteger(0, 1));
assertFalse(Compare.compareInteger(-1, 0));
assertFalse(Compare.compareInteger(1, 2));
assertFalse(Compare.compareInteger(-1, 1));
assertFalse(Compare.compareInteger(-2, -1));
}

public void testCompareWithLargeIntegers() {
assertTrue(Compare.compareInteger(Integer.MAX_VALUE, Integer.MAX_VALUE));
assertTrue(Compare.compareInteger(Integer.MAX_VALUE, 0));
assertTrue(Compare.compareInteger(Integer.MAX_VALUE, -1));
assertTrue(Compare.compareInteger(Integer.MAX_VALUE, Integer.MIN_VALUE));
assertFalse(Compare.compareInteger(0, Integer.MAX_VALUE));
assertFalse(Compare.compareInteger(-2, Integer.MAX_VALUE));

assertTrue(Compare.compareInteger(Integer.MIN_VALUE, Integer.MIN_VALUE));
assertFalse(Compare.compareInteger(Integer.MIN_VALUE, 0));
assertFalse(Compare
.compareInteger(Integer.MIN_VALUE, Integer.MAX_VALUE));
assertTrue(Compare.compareInteger(-1, Integer.MIN_VALUE));
assertTrue(Compare.compareInteger(0, Integer.MIN_VALUE));
}

public void testCompareWithRandomIntegers() {
Random random = new Random();
random.setSeed(Calendar.getInstance().getTimeInMillis());
int countOfTestDatas = 10000;
for (int i = 0; i < countOfTestDatas; i++) {
int a = random.nextInt();
int b = random.nextInt();
assertEquals(Compare.compareInteger(a, b), a >= b);
}
}
}


[解决办法]
终于做完了，累死了。。。

Java code
public class Test5 {    public static void main(String[] args) {        int a = -2147483648;        int b = 2147483647;        // a 和 b 是否相等，相等时 e 值为 0，否则为 1        // 采用对半位或，逐次降位进行计算        int e = a ^ b;        e = (e & 0xffff0000) >>> 16 | (e & 0x0000ffff);        e = (e & 0x0000ff00) >>>  8 | (e & 0x000000ff);        e = (e & 0x0000000f) >>>  4 | (e & 0x0000000f);        e = (e & 0x0000000c) >>>  2 | (e & 0x00000003);        e = (e & 0x00000002) >>>  1 | (e & 0x00000001);        // 进行比较，a 大时 k 值为 0，b 大时 k 值为 1，a 和 b 相等时 k 值为 0        int k = (~(a ^ b) >>> 31) * (a - b) >>> 31;        k += ((a ^ b) >>> 31) * (a >>> 31);        // 按照 <、=、> 的 ASCII 顺序，修正 ASCII 偏移量        // e = 0, k = 0 时表示相等，偏移 1        // e = 1, k = 0 时表示大于，偏移 2        // e = 1, k = 1 时表示小于，偏移 0        int offset = (e & (k ^ 1)) + (k ^ 1);        System.out.printf("%d %3$c %2$d%n", a, b, '<' + offset);        // System.out.println(a + " " + (char)('<' + offset) + " " + b);    }}
[解决办法]
我说我发的怎么这么别扭，原来这个编辑控件对chrome支持的不好，用IE重新发一个：
Java code
public class Compare {    // 使用boolean表示符号位，true为正，false为负    private static final boolean signToBool[] = { true, false };    // 取得整数的符号位    private static final boolean getSignOfInteger(int integer) {        return signToBool[integer >>> 31];    }    // 比较int1和int2大小，int1>=int2返回true，否则返回false    public static boolean compareInteger(int int1, int int2) {        boolean signOfInt1 = getSignOfInteger(int1);        boolean signOfInt2 = getSignOfInteger(int2);        boolean signInt1MinusInt2 = getSignOfInteger(int1 - int2);        // 原理很简单：符号相同返回int1-int2的符号位（为正表示int1>=int2）；不同返回int1的符号位        return (!(signOfInt1 ^ signOfInt2) && signInt1MinusInt2)                || ((signOfInt1 ^ signOfInt2) && signOfInt1);    }    public static int maxInteger(int int1, int int2) {        return compareInteger(int1, int2) ? int1 : int2;    }} 
 
[解决办法]
学习了，XX LZ
[解决办法]
挺尿性
(*^__^*) 嘻嘻……
[解决办法]
呵呵，再加一个
Java code
    // 比较int1和int2大小：大返回1，等返回0，小返回-1    public static int compareIntegerC(int int1, int int2) {        int signbitOfInt1 = int1 >>> 31;        int singbitOfInt2 = int2 >>> 31;        int signbitOfInt1MinusInt2 = (int1 - int2) >>> 31;        int signbitOfInt2MinusInt1 = (int2 - int1) >>> 31;        return singbitOfInt2 - signbitOfInt1                + ((1 - singbitOfInt2 + signbitOfInt1) & 1)                * (signbitOfInt2MinusInt1 - signbitOfInt1MinusInt2);    }
[解决办法]
UP

[解决办法]
学习了，好贴子。
[解决办法]
agree...
[解决办法]
接分！
[解决办法]
好啊  顶！
[解决办法]
新手上路，跟着学习了！
[解决办法]
一山还有一山高
菜鸟长见识了
[解决办法]
引用楼主 justinavril 的帖子:

原帖请见：看到一个面试题，大家来讨论下！ 
因为那个帖子太长了，我结了。这个帖子里主要贴几个典型的解法。 

我认为比较好的解法（在Blog里也写了这个方法：不用比较运算符，判断int型的a，b两数的大小） 

Java codepublic class Bigger {
    public static void main(String args[]){
        int a = -2147483648;
        int b = 2147483647;
        
        String[] strArray = {"a>=b", "a<b"};
      …

[解决办法]
学习了
[解决办法]
GOOD  !    study !
[解决办法]
mark
[解决办法]
markit
[解决办法]
int
  可有赋值那么大吗？
[解决办法]
up
[解决办法]
 帮顶一下！！！
[解决办法]
up下
[解决办法]
额滴天纳.

  额咱一点都不懂呢。  
  
         也快学了4个月了
[解决办法]
up!!!!!!1
[解决办法]
up下
[解决办法]
mark
[解决办法]
已经做了越界的判断（符号位相同的操作是不会越界的，越界主要是符号为不同的操作），做过3组测试（简单的比较、边界测试和10000组随机数的测试）都pass
探讨

你这个int1-int2要是越界了，结果还对吗？ 
引用:

呵呵，再加一个 

Java code 
    // 比较int1和int2大小：大返回1，等返回0，小返回-1  
 
    public static int compareIntegerC(int int1, int int2) { 
        int signbitOfInt1 = int1 >>> 31; 
        int singbitOfInt2 = int2 >>> 31; 
        int signbitOfInt1MinusInt2 = (int1 - int2) >>> 31; 
        int signbitOfInt2MinusInt1 = (…

[解决办法]
牛X！
[解决办法]
探讨

引用楼主 justinavril 的帖子:
还有些是用接口实现的，有点复杂了。有很多人会问，搞这个东西有什么实际的用途吗？是，确实没什么用，不如直接比较。但是有时候我们中国人就是被这种“有没有用”的功利主义给害了。研究数学，物理和化学有用吗？是没有直接的作用，但是你看看为什么美国，日本，德国的工业和高科技产业如此发达，还不是靠基础科学的投入吗？Google为了提高搜索算法的效率，也是投入巨资。不是什么东西有用没用就…

[解决办法]
不是什么东西有用没用就能简单的决定你去不去做一件事情，因为你不去做一件事情，就无法知道你在做这件事情的过程中会有什么收获。有一句话说的好：人生是曲折的，但生活是精彩的。
[解决办法]
Java code
public class Test2{    public static void main(String args[])    {        int a=1;        int b=2;        System.out.println(compareNumbers(3,33));    }    public static String compareNumbers(int a,int b)    {        String s1=String.valueOf(a);        String s2=String.valueOf(b);        int result=0;        String s=null;        //如果两个符号相同        if(!(s1.contains("-")^s2.contains("-")))        {            result=a-b;            if(String.valueOf(result).contains("-"))            {                s=a+"<"+b;            }            else if(String.valueOf(result).startsWith("0"))            {                s=a+"="+b;            }            else            {                s=a+">"+b;            }        }        else        {            if(s1.contains("-"))            {                s=a+"<"+b;            }            else            {                s=a+">"+b;            }        }        return s;    }}
[解决办法]
看到这个话题，觉得很有意思。

a、b两数正负符号出现情况，只可能是四种情形。
问题分情况讨论后，可以转化为更容易解决的子问题
我们知道，比较两个“非负整数”是容易的。

构思下面这个函数
 // 如果a>=b返回true，否则返回false
 public boolean ge(int a, int b) {
   int pos1 = (new int[][] { {
               0, 1}
               , {
               2, 3}
   }
       )[a >>> 31][b >>> 31];
   int m = (new int[] {
            1, 0, 0, 0})[pos1] * a + (new int[] {
                                      0, -1, 0, -1})[pos1] * b;
   int n = (new int[] {
            0, 0, -1, -1})[pos1] * a + (new int[] {
                                        1, 0, 0, 0})[pos1] * b;
   return (new boolean[] {true, false})[ (m - n) >>> 31];
 }
 

 

查看更多 下一篇