LeetCode刷题笔记(3)Java位运算符与使用按位异或(进制之间的转换)

摘要:
该算法应该具有线性时间复杂性,并且不使用额外的空间。当时,我用双指针尝试了以下操作,但失败了,因为最终结果可能是错误的。3.正确的解决思路是使用“按位XOR”,即Java中的“^”运算符进行计算。由于XOR的原理是差值为1,相同值为0,因此如果主题中给定数组中两个相同XOR的结果必须为0,则最终结果是只出现一次的元素。

  1.问题描述

  给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

  算法应该具有线性时间复杂度并且不使用额外空间。

输入: [4,1,2,1,2]
输出: 4

  2.解题思路

  这道题的主要的难点是具有线性时间复杂度并且不能使用额外的空间,因此就排除了很多的方法。

  当时使用双指针尝试了以下,但是并没有取得成功,因为最后的结果可能是错误的。

  3.正确解题思路

  使用“按位异或”,即Java中的‘^’运算符来进行计算。

  由于异或的原则是,不同为1,相同为0,题目中给定的数组中,如果两个相同的数异或的结果一定为0,最后得到的结果就是只出现一次的元素。

    public int singleNumber(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }

  4.另外的一个例子

  需要找出t中不在s中的那个字符。

输入:
s = "abcd"
t = "abcde"

输出:
e

  也可以用按位异或的方式进行计算

public char findTheDifference(String s, String t) {
    char c = 0;
    for (int i = 0; i < s.length(); ++i) {
        c ^= s.charAt(i);
    }
    for (int i = 0; i < t.length(); ++i) {
        c ^= t.charAt(i);
    }
    return c;
}

  5.问题描述

  不使用“+”“-”运算符计算两个整数的和。

  (1)自己的思路:模拟计算机实际来操作二进制数补码的加法

  Integer.parseInt无法将一个负数的补码转换成原始的负数,否则会报错java.lang.NumberFormatException

  此时,只能这么来计算:取反码,然后加1,转换成相反数,然后添加上一个符号“-”

//        System.out.println(new e371().getSum(a, b));
        System.out.println("11111111111111111111111111101100".length());
        System.out.println(Integer.toBinaryString(-20));
//        System.out.println(Integer.parseInt("11111111111111111111111111101100", 2));
        System.out.println(Integer.parseInt("00000000000000000000000000010100", 2));

   解题思路:模仿实际计算机的真实计算结果,超级麻烦!!!!!!

class Solution {
    public int getSum(int a, int b) {
        
        String aStr = Integer.toBinaryString(a);
        String bStr = Integer.toBinaryString(b);
        String longStr  = (aStr.length() < bStr.length()) ? bStr : aStr; 
        String shortStr = (aStr.length() < bStr.length()) ? aStr : bStr; 
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < longStr.length() - shortStr.length(); i++) {
            sb.append(0);
        }
        shortStr = sb.toString().concat(shortStr);
        
        boolean isUp = false;
        StringBuffer resSB = new StringBuffer();
        for (int i = longStr.length() - 1; i >= 0; i--) {
            if (!isUp) {
                if (longStr.charAt(i)== '1' && shortStr.charAt(i) == '1') {
                    isUp = true;
                    resSB.append(0);
                } else {
                    resSB.append(Integer.valueOf(longStr.charAt(i)) ^ Integer.valueOf(shortStr.charAt(i)));
                }
            } else {
                if (longStr.charAt(i) == '1' && shortStr.charAt(i) == '1') {
                    isUp = true;
                    resSB.append(1);
                }  else if (longStr.charAt(i) == '0' && shortStr.charAt(i)== '0') {
                    resSB.append(1);
                    isUp = false;
                }  else {
                    resSB.append(0);
                    isUp = true;
                }
            }
        }
        
        if (isUp && resSB.length() < 32) resSB.append(1);
        String result = resSB.reverse().toString();
        if (result.length() < 32) {
            return Integer.parseInt(result, 2);
        }
        if (result.charAt(0) == '0') {
            return Integer.parseInt(result, 2);
        } else {
            StringBuffer sbsb = new StringBuffer();
            for (char c : result.toCharArray()) {
                if (c == '1') {
                    sbsb.append(0);
                } else {
                    sbsb.append(1);
                }
            }
            result = sbsb.toString();
            
            longStr = result;
            shortStr = "00000000000000000000000000000001";
            
            boolean isUp_1 = false;
            StringBuffer resSB_1 = new StringBuffer();
            for (int i = longStr.length() - 1; i >= 0; i--) {
                if (!isUp_1) {
                    if (longStr.charAt(i)== '1' && shortStr.charAt(i) == '1') {
                        isUp_1 = true;
                        resSB_1.append(0);
                    } else {
                        resSB_1.append(Integer.valueOf(longStr.charAt(i)) ^ Integer.valueOf(shortStr.charAt(i)));
                    }
                } else {
                    if (longStr.charAt(i) == '1' && shortStr.charAt(i) == '1') {
                        isUp_1 = true;
                        resSB_1.append(1);
                    }  else if (longStr.charAt(i) == '0' && shortStr.charAt(i)== '0') {
                        resSB_1.append(1);
                        isUp_1 = false;
                    }  else {
                        resSB_1.append(0);
                        isUp_1 = true;
                    }
                }
            }
            result = resSB_1.reverse().toString();
            return -Integer.parseInt(result, 2);
        }
    }
}

   (2)更好的思路,使用位运算符

    public int getSum(int a, int b) {
        if(b == 0){            //没有进位的时候完成运算
            return a;
        }
        int sum,carry;
        sum = a^b;            //完成第一步加法的运算
        carry = (a&b)<<1;    //完成第二步进位并且左移运算
        return getSum(sum,carry);//
    }

  根据实际例子分析这块代码:

(1)a=1,b=2
    a-> 00000000 00000000 00000000 00000001
    b-> 00000000 00000000 00000000 00000010
b=2
   sum-> 00000000 00000000 00000000 00000011
a&b-> 00000000 00000000 00000000 00000000
carry-> 00000000 00000000 00000000 00000000 输出sum=3

(2)a=1,b=7
    a-> 00000000 00000000 00000000 00000001
    b-> 00000000 00000000 00000000 00000111
   a&b->  00000000 00000000 00000000 00000001
   sum-> 00000000 00000000 00000000 00000110
carry-> 00000000 00000000 00000000 00000010

   a&b-> 00000000 00000000 00000000 00000010
   sum-> 00000000 00000000 00000000 00000100
carry-> 00000000 00000000 00000000 00000100
   a&b-> 00000000 00000000 00000000 00000100
   sum-> 00000000 00000000 00000000 00000000
carry-> 00000000 00000000 00000000 00001000
   a&b-> 00000000 00000000 00000000 00000000
   sum-> 00000000 00000000 00000000 00001000
carry-> 00000000 00000000 00000000 00000000 输出sum = 8

(3)a=-16,b=14
    a-> 11111111111111111111111111110000
    b-> 00000000000000000000000000001110
   a&b-> 00000000000000000000000000000000
   sum-> 11111111111111111111111111111110
carry-> 0 输出sum=-2

  6.Java位运算符

  (1)"~(按位取反)"

~(-14) == 13(int类型)
-14(原码):10000000  00000000  00000000  00001110
-14(反码):11111111  11111111  11111111  11110001
-14(补码):11111111  11111111  11111111  11110010
非过程(同时为1才为1):00000000 00000000 00000000 00001101
十进制表示为:1+4+8=13

  (2)"&(按位与)"

5&-4 == 4(int类型)
-4(原码):10000000 00000000 00000000 00000100
-4(反码):11111111 11111111 11111111 11111011
-4(补码):11111111 11111111 11111111 11111100
5 : 00000000 00000000 00000000 00000101 -4: 11111111 11111111 11111111 11111100 与过程(同时为1才为1): 00000000 00000000 00000000 00000100 十进制表示为:4

  (3)"|(按位或)"

3|6 == 7(int类型)
3: 00000000  00000000  00000000  00000011
6: 00000000  00000000  00000000  00000110
或过程(只要有1就为1):
   00000000  00000000  00000000  00000111
十进制表示为:1+2+4=7

  (4)"^(按位异或)"

10^3 == 9(int类型)
3 : 00000000  00000000  00000000  00000011
10: 00000000  00000000  00000000  00001010
异或过程(不同为1相同为0):
    00000000  00000000  00000000  00001001
十进制表示为:1+8=9

  (5)"<<(左移,低位添0补齐)"

-2<<3 == -16(int类型)
-2 : 11111111 11111111 11111111 11111110
<<过程:111(舍弃)  11111111  11111111  11111111  11110 000(补零)
十进制表示为:-16

  (6)">>(右移,高位添符号位)"

15>>2 == 3(int类型)
15 : (符号位是0)00000000  00000000  00000000  00001111
>>过程:00(补两个0) 000000 00000000 00000000 00000011 11(舍弃最末位两个11)
十进制表示为:1+2=3

  (7)">>>(右移,高位添0补齐)"

4>>>2 == 1(int类型)
4 : 00000000  00000000  00000000  00000100
>>>过程:00(补两个0) 000000 00000000 00000000 00000001 00(舍弃最末位两个00)
十进制表示为:1

免责声明:文章转载自《LeetCode刷题笔记(3)Java位运算符与使用按位异或(进制之间的转换)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇TCP keepalive长连接心跳保活MySQL多实例启动停止下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

oracle double和float,number 羽毛

float,double,number都是oracle的数值类型。1个汉子=2个英文=2个字节float表示单精度浮点数在机内占4个字节,用32位二进制描述。 double表示双精度浮点数在机内占8个字节,用64位二进制描述。 1、只有一个参数时,如NUMBER(24)。表示所定义的数字最大可设置24位整数。2、有两个参数时,如NUMBER(38, 3)。...

计算机基础知识:原码、反码、补码

可能很多人有这样的疑问,我们为什么要了解原码、反码、补码,它能帮助我们解决什么问题?在编写代码中有什么实际用途呢? 我是这样认为的,其一,作为计算机基础知识,我们必须有所了解。其二、这些基础知识无论是普通的编写代码,还是研究高超的算法都离不开它。 例:我们常见的位运算 按位与(&)、按位或(|)、取反(~)等等。 在代码中, 我们可能经常会碰到这样...

c语言运算符

1.运算符概述 运算符是一种编译器执行特定的数学或逻辑操作的符号。C语言提供了以下类型的运算符: 算术运算符 关系运算符 逻辑运算符 位运算符 赋值运算符 条件运算符 其他运算符 2.算术运算符 算术运算符分为单目运算符和双目运算符,单目运算符表示只需要一个操作数,双目运算符需要两个操作数。 2.1 双目算术运算符 1)+ :加法,把两个操作数相加...

ORACLE LOB 大对象处理

LOB大对象处理:主要是用来存储大量数据的数据库字段,最大可以存储4G字节的非结构化数据。主要介绍字符类型和二进制文件类型LOB数据的存储,单独介绍二进制类型LOB数据的存储。一. Oracle中的LOB数据类型分类1,按存储数据的类型分:①字符类型:CLOB:存储大量单字节字符数据。NLOB:存储定宽多字节字符数据。②二进制类型:BLOB:存储较大无结...

Java动手实验及课后程序

课后作业 一、编写程序,消息框显示计算结果 设计思想:导入Scanner包,使用JOptionPane类来实现消息框的输入和结果的显示。 程序代码: package com; import java.util.Scanner; //导入Scanner包 import javax.swing.JOptionPane; public class Manner ...

交换函数

问题描述: 假设有两个整数A=8,B=9 ,现在要交换A和B的值,使得A=9,B=8. 原理分析: 方法一:利用一个辅助空间C,然后先将A中的数据放在C中,然后再将B中的数据放到A中,最后再将C中的数据放到A中,这样就可以实现数据的交换了。 C语言代码实现(子函数): 点击(此处)折叠或打开 void swap1(datatype *a,dataty...