剑指offer java版 test11—二进制 原码 反码 补码（好多种方法，好多知识扩展与漏洞，建议我自己时常温故！）

题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
知识回顾：先回顾一下二进制方面的知识。

计算机种的有符号数有三种表示方法，即原码，反码和补码。三种表示方法均有符号位和数值位两部分，符号位都是用0表示正，用1表示负，而数值位，三种表示方法各不相同.


原码：原码就是符号位加上真值的绝对值。、

反码：正数的反码是其本身，负数的反码是在其原码的基础上，符号位不变，其余各个位取反

补码：正数的补码就是其本身，负数的补码是在其原码的基础上，符号位不变，其余位取反，最后+1（即在反码的基础上加1）


左移运算符<<：将一个运算对象的各二进制位全部左移若干位（左边的二进制丢弃，右边补0）（相当于乘以2）

右移运算符>>：将一个运算对象的各二进制位全部右移若干位，正数左补0，负数左补1（因为负数的符号位总是1）


位运算：都为1时，结果才为1   比如10&9=8


思路：正数好说。关于负数，该如何求取补码呢？用上述方式求取补码在编程上不方便。所以采用下面这种方式来求负数的补码：


*先求出负数绝对值的原码

* 再从原码的最后一位数码往前数，当约到第一个1时停在此位置。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

* 再将第一个1前面的数码全部求反


后来看了很多大佬的思路，收益颇多。 这里利用右移和位运算做一下

（比较有意思的是，java里面自带了个函数Integer.bitCount()函数，可以直接求出来。。。。这里先不使用了）

4.1 首个失败代码（没考虑负数右移后会补1，导致代码无限循环）
package cn.test10;

public class test {
    public static void main(String[] args){
        Solution sl=new Solution();
        System.out.println(sl.NumberOf1(3));
    }
}

class Solution{
    public int NumberOf1(int n){
       int count=0;
       while(n!=0){
          if((n&1)==1){
                count++;
           }
          n=n>>1;
        }
       return count;
    }
}

4.2  反向思考，用1的左移和n进行位运算（因为1时正数，左移都是补0，1的左移和n位运算的结果为0时，表示n的当前位是0，不为0时，表示n的当前位是1，注意：1的左移与m的位运算结果并不是0或1，而是任何非负整数，但是只要结果不为0，则可说明n的当前位为1）
缺点：条件循环那里，需要一直循环32次，因为int类型是32位，直到1左移32次后变成0，跳出while循环
package cn.test10;

public class test {
    public static void main(String[] args){
        Solution sl=new Solution();
       System.out.println(sl.NumberOf1(3));

    }
}

class Solution{
    public int NumberOf1(int n){
       int count=0;
       int flag=1;
       while(flag!=0){
          if((n&flag)!=0){
                count++;
           }
          flag=flag<<1;
        }
       return count;
    }
}

4.3 那么究极版最佳答案来了，我暂时未能消化，所以直接贴上大佬的分析的图片。（就好像原先是1，减1后是0，与运算后，为0；要是原先为0，减1后是1，与运算后，为0；即每次与运算，都可以将二进制数最右边的1变为0，那么能进行多少次这样的运算，就代表有多少个1，即可结束循环）

数在计算机中是以二进制形式表示的。 

数分为有符号数和无符号数。 

原码、反码、补码都是有符号定点数的表示方法。 

一个有符号定点数的最高位为符号位，0是正，1是副。 


以下都以8位整数为例， 


原码就是这个数本身的二进制形式。 

例如

0000001 就是+1

1000001 就是-1 


正数的反码和补码都是和原码相同。 

负数的反码是将其原码除符号位之外的各位求反


[-3]反=[10000011]反=11111100 
负数的补码是将其原码除符号位之外的各位求反之后在末位再加1。


[-3]补=[10000011]补=11111101 

一个数和它的补码是可逆的。 


为什么要设立补码呢？ 


第一是为了能让计算机执行减法： 

[a-b]补=a补+（-b）补 


第二个原因是为了统一正0和负0 

正零：00000000 

负零：10000000 

这两个数其实都是0，但他们的原码却有不同的表示。 

但是他们的补码是一样的，都是00000000 

特别注意，如果+1之后有进位的，要一直往前进位，包括符号位！（这和反码是不同的！） 

[10000000]补 

=[10000000]反+1 

=11111111+1 

=(1)00000000 

=00000000(最高位溢出了，符号位变成了0） 


有人会问 

10000000这个补码表示的哪个数的补码呢？ 

其实这是一个规定，这个数表示的是-128 

所以n位补码能表示的范围是 

-2^(n-1)到2^(n-1)-1 

比n位原码能表示的数多一个
又例：

1011 

原码：01011 

反码：01011 //正数时，反码＝原码 

补码：01011 //正数时，补码＝原码 


-1011 

原码：11011 

反码：10100 //负数时，反码为原码取反 

补码：10101 //负数时，补码为原码取反＋1 


0．1101 

原码：0.1101 

反码：0.1101 //正数时，反码＝原码 

补码：0.1101 //正数时，补码＝原码 


-0．1101 

原码：1.1101 

反码：1.0010 //负数时，反码为原码取反 

补码：1.0011 //负数时，补码为原码取反＋1
总结：

在计算机内，定点数有3种表示法：原码、反码和补码
所谓原码就是前面所介绍的二进制定点表示法，即最高位为符号位，“0”表示正，“1”表示负，其余位表示数值的大小。
反码表示法规定：正数的反码与其原码相同；负数的反码是对其原码逐位取反，但符号位除外。
补码表示法规定：正数的补码与其原码相同；负数的补码是在其反码的末位加1。
1、原码、反码和补码的表示方法
（1）       原码：在数值前直接加一符号位的表示法。
例如：         符号位     数值位
[+7]原=      0       0000111     B
[-7]原=      1       0000111     B
        注意：a. 数0的原码有两种形式：
                      [+0]原=00000000B       [-0]原=10000000B
                  b. 8位二进制原码的表示范围：-127～+127
2）反码：
        正数：正数的反码与原码相同。
        负数：负数的反码，符号位为“1”，数值部分按位取反。
例如： 符号位      数值位
        [+7]反=     0      0000111     B
        [-7]反=     1      1111000     B
注意：a. 数0的反码也有两种形式，即
                 [+0]反=00000000B
                 [- 0]反=11111111B
             b. 8位二进制反码的表示范围：-127～+127
3）补码的表示方法
1）模的概念：把一个计量单位称之为模或模数。例如，时钟是以12进制进行计数循环的，即以12为模。在时钟上，时针加上（正拨）12的整数位或减去（反拨）12的整数位，时针的位置不变。14点钟在舍去模12后，成为（下午）2点钟（14=14-12=2）。从0点出发逆时针拨10格即减去10小时，也可看成从0点出发顺时针拨2格（加上2小时），即2点（0-10=-10=-10+12=2）。因此，在模12的前提下，-10可映射为+2。由此可见，对于一个模数为12的循环系统来说，加2和减10的效果是一样的；因此，在以12为模的系统中，凡是减10的运算都可以用加2来代替，这就把减法问题转化成加法问题了（注：计算机的硬件结构中只有加法器，所以大部分的运算都必须最终转换为加法）。10和2对模12而言互为补数。
同理，计算机的运算部件与寄存器都有一定字长的限制（假设字长为8），因此它的运算也是一种模运算。当计数器计满8位也就是256个数后会产生溢出，又从头开始计数。产生溢出的量就是计数器的模，显然，8位二进制数，它的模数为28=256。在计算中，两个互补的数称为“补码”。
2）补码的表示： 正数：正数的补码和原码相同。
       负数：负数的补码则是符号位为“1”，数值部分按位取反后再在末位（最低位）加1。也就是“反码+1”。
例如：     符号位 数值位
[+7]补=      0      0000111     B
         [-7]补=      1      1111001     B
补码在微型机中是一种重要的编码形式，请注意：
a.采用补码后，可以方便地将减法运算转化成加法运算，运算过程得到简化。正数的补码即是它所表示的数的真值，而负数的补码的数值部份却不是它所表示的数的真值。采用补码进行运算，所得结果仍为补码。
b.与原码、反码不同，数值0的补码只有一个，即          [0]补=00000000B。
c.若字长为8位，则补码所表示的范围为-128～+

数值在计算机中表示形式为机器数,计算机只能识别0和1,使用的是二进制,而在日常生活中人们使用的是十进制,"正如亚里士多德早就指出的那样,今天十进制的广泛采用,只不过我们绝大多数人生来具有10个手指头这个解剖学事实的结果.尽管在历史上手指计数(5,10进制)的实践要比二或三进制计数出现的晚."(摘自<<数学发展史>>有空大家可以看看哦~,很有意思的).为了能方便的与二进制转换,就使用了十六进制(2 4)和八进制(23).下面进入正题.
数值有正负之分,计算机就用一个数的最高位存放符号(0为正,1为负).这就是机器数的原码了.假设机器能处理的位数为8.即字长为1byte,原码能表示数值的范围为
(-127~-0 +0~127)共256个.
   有了数值的表示方法就可以对数进行算术运算.但是很快就发现用带符号位的原码进行乘除运算时结果正确,而在加减运算的时候就出现了问题,如下: 假设字长为8bits
( 1 ) 10-   ( 1 )10 =   ( 1 )10 + ( -1 )10 =   ( 0 )10
(00000001)原 + (10000001)原 = (10000010)原 = ( -2 ) 显然不正确.
   因为在两个整数的加法运算中是没有问题的,于是就发现问题出现在带符号位的负数身上,对除符号位外的其余各位逐位取反就产生了反码.反码的取值空间和原码相同且一一对应. 下面是反码的减法运算:
( 1 )10 -   ( 1 ) 10=   ( 1 ) 10+ ( -1 ) 10=   ( 0 )10
(00000001) 反+ (11111110)反 =   (11111111)反 =   ( -0 )   有问题.
( 1 )10 -   ( 2)10 =   ( 1 )10 + ( -2 )10 =   ( -1 )10
(00000001) 反+ (11111101)反 =   (11111110)反 =   ( -1 ) 正确
问题出现在(+0)和(-0)上,在人们的计算概念中零是没有正负之分的.(印度人首先将零作为标记并放入运算之中,包含有零号的印度数学和十进制计数对人类文明的贡献极大).
于是就引入了补码概念. 负数的补码就是对反码加一,而正数不变,正数的原码反码补码是一样的.在补码中用(-128)代替了(-0),所以补码的表示范围为:
(-128~0~127)共256个.
注意:(-128)没有相对应的原码和反码, (-128) = (10000000)   补码的加减运算如下:
( 1 ) 10-   ( 1 ) 10=   ( 1 )10 + ( -1 )10 =   ( 0 )10
(00000001)补 + (11111111)补 =   (00000000)补 = ( 0 ) 正确
( 1 ) 10-   ( 2) 10=   ( 1 )10 + ( -2 )10 =   ( -1 )10
(00000001) 补+ (11111110) 补=   (11111111)补 = ( -1 )   正确
 所以补码的设计目的是:
⑴使符号位能与有效值部分一起参加运算,从而简化运算规则.
⑵使减法运算转换为加法运算,进一步简化计算机中运算器的线路设计
   所有这些转换都是在计算机的最底层进行的，而在我们使用的汇编、C等其他高级语言中使用的都是原码。看了上面这些大家应该对原码、反码、补码有了新的认识了吧！
#######################################################################

计算机系统内部采用二进制表示数值数据，也采用二进制编码表示非数值数据和指令。计算机中存储信息的最小单位称为位。位分别代表0和1两种状态。数值数据分为有符号数和无符号数。无符号数最高位表示数值，而有符号数最高位表示符号。有符号数有不同的编码方式，常用的是补码。

(1)原码:

   最高位表示符号(正数用0,负数用1),其他位表示数值位,称为有符号数的原码表示法.

   例:X=45=00101101B   [X]原=00101101B

      X=-45,[X]原=10101101B

原码表示简单易懂,但若是两个异号数相加(或两个同号数相减),就要做减法.为了把减法运算转换为加法运算就引进了反码和补码.

(2)反码:

    正数的反码与原码相同,符号位用0表示,数值位值不变.负数的反码符号位用1表示,数值位为原码数值位按位取反形成,即0变1,1变0.

   例:X=45=00101101B   [X]反=00101101B

      X=-45,[X]反=11010010B

(3)补码:

   正数的补码与原码相同,即符号用0表示,数值位值不变.负数的补码为反码加1形成.

   例:X=45=00101101B   [X]补=00101101B

      X=-45,[X]反=11010011B

补充点感觉这样就完全了，文章写的不错对于程序设计就应该了解这些！

今天看了java中的二进制操作，突然发现本科上电路课程的时候就没有理解计算机采用补码存储二进制数的原因，以及补码的推导。这次算是补课了。

1 补码的概念

正数的补码是其本身
负数的补码：原码->反码->补码（符号为变为1，除符号位取反，加1）

补码本身就是分段函数，相当于专为负数设计。
2 使用补码的原因

减法可以变成负数的加法，因此加法和减法可以统一处理。
使用补码，可以将符号位和数值域统一处理，不需要单独计算符号位（原因看后面补码的推导过程）。
补码与原码相互转换，其运算过程是相同的，不需要额外的硬件电路。

3 补码的推导
3.1 模
模是指一个计量系统的计数范围。如时钟等。计算机也是一个计算器，它也是有一个计量范围，即都存在一个“模”。如时钟的计量范围是0~11，模=12。32位计算机的计量范围是232，模=232。“模”是计量器产生“溢出”的量，它的值在计量器上表示不出来，计量器上只能表示出模的余数，如12的余数有0,1,2,3,4,5,6,7,8,9,10,11。
3.2 补数
补码将二进制数的正负号放入符号位中，在推导过程中，我们先不把减法转化为负数的加法，而是通过对二进制数的减法推导出负二进制数的补码。
假设当前时针指向11点，而准确时间是8点，调整时间可有以下两种拨法：一种是倒拨3小时，即：11-3=8。另一种是顺拨9小时：11+9=12+8=8。在以模为12的系统中，加9和减3效果是一样的，因此凡是减3运算，都可以用加9来代替。对“模”12而言，9和3互为补数（二者相加等于模）。所以我们可以得出一个结论，即在有模的计量系统中，减一个数等于加上它的补数，从而实现将减法运算转化为加法运算的目的。
3.3 补码的推导
假设我们的寄存器位数为4，即最多可以存4位的二进制数，则其计量范围即模是2^4=16。由于最左边位用于存放符号位，所以其能够表示的范围是-7～8。现在以计算5-3为例进行推导。
 # 按以上理论，减一个数等于加上它的补数，所以
 5 - 3
 # 等价于 
 5 + (16 - 3)   // 算术运算单元将减法转化为加法
 # 用二进制表示则为：
 0101 + (10000 - 0011)
 # 等价于
 0101 + ((1 + 1111) - 0011)
 # 等价于
 0101 + (1 + (1111 - 0011))
 # 等价于
 0101 + (1 + 1100) // 括号内是3（0011）的反码+1，正是补码的定义
 # 等价于
 0101 + 1101
 # 因为5-3等价于5+(-3)，所以
 -3 = 1101
 # 即 `-3` 在计算机中的二进制（补码）为 `1101`。
 # 最后一步 0101 + 1101 等于
 10010

因为我们的寄存器是4位的，第一位“溢出”了，所以我们只保存了4位，即0010，而当计算机去读取时这正是我们所期望的2。
4 "0"的补码
在计算机中，有+0和-0之分。

+0:原码，反码，补码均为0000.
-0:原码1000，反码1111，补码0000.

可以看到0的补码只有一个，而原码有两个。这就产生了一个问题，4位的二进制数的补码个数比原码个数多一个，例如1000（对于原码是0，对于补码我们通常将其设为-8）。这就可以解释int的范围问题。
5 有符号左移、有符号右移，无符号右移
由于计算机中存储二进制的补码，因此执行有符号的左移和右移相当于在保证符号的情况下进行幂运算。

源码
原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 

[+1] 的原码 = 0000 0001
[-1] 的原码 = 1000 0001



第一位是符号位. 因为第一位是符号位, 所以8位二进制数的取值范围就是:
[1111 1111 , 0111 1111]
即
[-127 , 127]


反码

正数的反码是其本身
负数的反码是在其原码的基础上, 符号位不变，其余各个位取反.
[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反


补码
正数的补码就是其本身
负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)。

[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补


【-1】  原码 10000001 反码11111110 补码 11111111

【3】   原码 00000011 反码 00000011 补码 00000011

【-127】原码11111111 反码 10000000 补码 10000001

【127】 原码 01111111 反码 01111111 补码 01111111


首先要明白一点，二进制移位操作都是针对存储在计算机中中二进制的操作，
那么就要知道，正数在计算机中是用二进制表示的，负数在计算机中使用补码表示的。


左移位：<<  ，有符号的移位操作

左移操作时将运算数的二进制码整体左移指定位数，左移之后的空位用0补充


右移位：>>  ，有符号的移位操作

右移操作是将运算数的二进制码整体右移指定位数，右移之后的空位用符号位补充，如果是正数用0补充，负数用1补充。

	public static void main(String[] args) {
		
		System.out.println(3<<2);//3左移2位
		System.out.println(-3<<2);//-3左移2位
		
		System.out.println(6>>2);//6右移2位
		System.out.println(-6>>2);//-6右移2位
		   
	}
12
-12
1
-2


解释：
1>
3 正数，在计算机中用二进制表示

00000000 00000000 00000000 00000011
00 00000000 00000000 00000000 00001100   左移两位右边补00  结果为12   2 的3次方 + 2的2次方 = 12


2> 
-3 负数 ，在计算机中用二进制补码表示
求-3的补码，根据上面的方法  负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1.
10000000 00000000 00000000 00000011   -3源码
11111111 11111111 11111111 11111100   -3反码
11111111 11111111 11111111 11111101   -3补码
11 11111111 11111111 11111111 11110100  左移两位右边补00     


这个数第一位是1 说明是个负数，那就是某个负数的补码。求出源码就能知道是哪个负数
11111111 11111111 11111111 11110011   减一，取得反码
10000000 00000000 00000000 00001100   第一位不变，其他为取反。得到 源码。
所以此负数为 -12


3>.
6 为正数，在计算机中显示二进制
00000000 00000000 00000000 00000110   6的源码
00000000 00000000 00000000 00000001   右移两位，正数右移，左边补0 。
所以答案为 1 


4> .
-6  位负数，在计算机中应该显示补码
00000000 00000000 00000000 00000110   6 的源码
负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1
求出补码
11111111 11111111 11111111 11111010  -6 的补码
负数右移，左边空缺用1补充
11111111 11111111 11111111 11111110   此为答案数字的补码。是个负数
求此负数源码
10000000 00000000 00000000 00000010  此为答案 -2