位运算-不做比较判断得到两个数中的大数

2022-6-3 diaba 笔试题 

package com.jiucaiyuan.net.question;

/**
 *
 * 题目：给定两个有符号32位整数a和b，返回a和b较大的一个
 * 要求：不用做任何比较判断
 *
 * &（与）、|（或）、~（非）和 ^（异或）
 *
 * @Author jiucaiyuan  2022/6/3 23:13
 * @mail services@jiucaiyuan.net
 */

public class GetMax {

    /**
     * 请保证参数n，不是1就是0的情况下
     * 1 ——> 0
     * 0 ——> 1
     * （位运算：
     * @param n
     * @return
     */
    public static int flip(int n){
        return n^1;
    }

    /**
     * n是非负数，返回1
     * n是负数，返回0
     *
     * n>>31   n这个数的符号位到达最右侧位置
     * @param n
     * @return
     */
    public static int sign(int n){
        return flip(   (n>>31) & 1    );
    }

    /**
     * 得到a和b较大的一个值
     * @param a
     * @param b
     * @return
     */
    public static int getMax1(int a ,int b){
        int c = a - b;  //本方法问题：a-b可能溢出
        int scA = sign(c);   //a-b为非负，scA为1，a-b为负，scA为0
        int scB = flip(scA); //scA为0，scB为1，scA为1，scB为0
        //scA为0，scB必为1，scA为1，scB必为0
        return a * scA + b * scB;
    }

    /**
     * 得到a和b较大的一个值
     * 此方法考虑了a-b溢出的情况
     * @param a
     * @param b
     * @return
     */
    public static int getMax2(int a ,int b){
        int c = a - b;
        int sA = sign(a);
        int sB = sign(b);
        int sC = sign(c);
        int difSab = sA ^ sB;  //a和b符号不一样，为1，一样为0
        int sameSab = flip(difSab); //a和b符号一样，为1，不一样，为0
        int returnA = difSab * sA + sameSab * sC; // a和b符号不同，a非负返回a，a和b符号相同，差值非负时返回a
        int returnB = flip(returnA);   //不返回a时，返回b
        return a * returnA + b * returnB;
    }

    public static void main(String[] args) {
        int a = -16;
        int b = 1;
        System.out.println(getMax1(a,b));
        System.out.println(getMax2(a,b));
        a = 2147483647;
        b = -2147480000;
        System.out.println(getMax1(a,b));   //a-b溢出了，返回结果错误
        System.out.println(getMax2(a,b));
    }

}

« 位运算-判断数是否是2的幂、4的幂 | 笔试题-田忌赛马»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022