2019獨角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>

文章看過后感覺受益匪淺，所以留下了以備溫故：http://www.congmo.net/blog/2012/03/11/Long-ByteShifting/

本篇主要講述位移運算在Long中所扮演的重要角色，有些出神入化的我根本無法理解，但是我一直秉承著無論對錯都要記錄思考的過程的宗旨寫每一篇文章。這一篇也不例外，讀Long這個類確實需要比較廣泛的知識面，我也是一邊在OSChina和stackoverflow上提問，一邊慢慢的鉆研，難免會存在偏差。

先來看個簡單的。

public static int signum(long i) {// HD, Section 2-7return (int) ((i >> 63) | (-i >>> 63)); }

這個函數(shù)作用就是返回參數(shù)i的符號，如果返回-1則是負(fù)數(shù)，如果返回0則是0，如果返回1則是正數(shù)。算法就是(int) ((i >> 63) | (-i >>> 63))，如果是正數(shù)的話i有符號右移63位后為0，-i無符號右移63位之后結(jié)果為1，或操作之后結(jié)果就是1.如果i為負(fù)數(shù)，那么有符號右移63位后就變成了1，然后-i無符號右移63位后就只剩下符號位，最后做或(|)操作結(jié)果就是-1. 如果參數(shù)i為0，那么移位后結(jié)果就是0.

System.out.println(Long.signum(100L)); System.out.println(Long.signum(0L)); System.out.println(Long.signum(-100L)); ? 輸出結(jié)果：
1
0
-1

接著是一個很少用到，但是實現(xiàn)方式不錯的兩個方法，循環(huán)左移和循環(huán)右移方法。

public static long rotateLeft(long i, int distance) {return (i << distance) | (i >>> -distance); } public static long rotateRight(long i, int distance) {return (i >>> distance) | (i << -distance); }

實現(xiàn)的代碼量可以說已經(jīng)精簡到最少了，有一點要注意的是，循環(huán)移位時，參數(shù)distance可以接受負(fù)數(shù)，當(dāng)distance為負(fù)數(shù)時，這個等式是成立的，rotateLeft(i, distance) = rotateRight(i, -distance)。這個方法中有兩點值得借鑒的，第一從整體上講循環(huán)移位的實現(xiàn)方式；第二是distance與-distance的巧妙運用。

就拿循環(huán)左移先來說說第二點吧，前置條件，我們首先假設(shè)distance大于0，起先我是很不理解i >>> -distance的，后來在stackoverflow上發(fā)問，有人給出了解釋，在移位的時候，如果distance小于0，會根據(jù)被移位數(shù)的長度進行轉(zhuǎn)換。就比如說這里我們對long進行移位，那么-distance就會被轉(zhuǎn)換成(64 + distance)(注，這里的distance是小于0的)。這樣的話，如果distance大于0時，(i << distance) | (i >>> -distance);就會被轉(zhuǎn)化成(i << distance) | (i >>> 64 + distance);

清楚了第二點，那么第一點也就不難理解了。用一幅圖來解釋循環(huán)左移。

在distance大于0的前提下，先左移distance位，然后再右移64-distance，最終用或運算相加，就是循環(huán)移位的結(jié)果。圖中為了省事兒用了8位做了個演示，先左移3位，然后右移(8-3)位，或運算之后就是結(jié)果啦。關(guān)于-distance在stackoverflow上的提問在這里。

下面是個更給力的方法-reverse(long i)，可以說就是高效率的化身。

public static long reverse(long i) {// HD, Figure 7-1i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L;i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL;i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL;i = (i << 48) | ((i & 0xffff0000L) << 16) |((i >>> 16) & 0xffff0000L) | (i >>> 48);return i; }

從整體上說，這個reverse方法集移位與二分算法于一身，堪稱經(jīng)典。 第一步以單位為單位，奇偶位交換 第二步以兩位為單位，完成前后兩位的交換。 第三步以四位為單位，完成前后四位的交換。 第四步以八位為單位，完成前后八位的交換。 最后一步?jīng)]有按常理繼續(xù)二分，而是通過一個轉(zhuǎn)換一步就完成了以16和32位為單位的交換。進而結(jié)束了整個64位的反轉(zhuǎn)。

現(xiàn)在一步一步剖析都是如何實現(xiàn)的。

i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L;

16進制的5為0101，或操作前半部分首先取出i的所有奇數(shù)位，然后整體左移一位，這樣實現(xiàn)i的奇數(shù)位左移一位變成偶數(shù)位；或操作后半部分先右移，即將偶數(shù)位右移變成奇數(shù)位，然后再取出奇數(shù)位。這樣就完成了64位中奇數(shù)位與偶數(shù)位的交換。

i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L;
這句同樣是實現(xiàn)交換，只不過3對應(yīng)的16進制為0011，即本次交換以2個字節(jié)為單位，交換完成了4個字節(jié)的反轉(zhuǎn)。 Liquid error: Flag value is invalid: -O ”” 直到這行代碼，實現(xiàn)了以字節(jié)為單位的反轉(zhuǎn)，最后僅僅使用一行代碼就實現(xiàn)了一兩個字節(jié)和四個字節(jié)為單位的反轉(zhuǎn)。 為了方便畫圖，現(xiàn)在對操作進行編號，另外從以字節(jié)為單位交換開始，之前的細(xì)節(jié)忽略。
(i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL; (i << 48) (i & 0xffff0000L) << 16) (i >>> 16) & 0xffff0000L) (i >>> 48); 這幅圖描述每個編號代碼執(zhí)行之后64位的變化。

不多做解釋，由于這個reverse的最后一行不是按常理”出牌”，所以我使用純粹的二分法來實現(xiàn)reverse。
public static long reverse(long i) {// HD, Figure 7-1i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L;i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L;i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL;i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL;i = (i & 0x0000ffff0000ffffL) << 16 | (i >>> 16) & 0x0000ffff0000ffffL;i = (i & 0x00000000ffffffffL) << 32 | (i >>> 32) & 0x00000000ffffffffL;return i; }

至于為什么要采用那種方式，而不是用”純粹”的二分法，在stackoverflow上有人提到，可能是因為前一種實現(xiàn)方式需要9個操作，而后一種實現(xiàn)方式需要10個操作。具體是出于怎樣的目的可能只有作者才知道。關(guān)于reverse我在stackoverflow上的提問在這里。

最后看一個方法。

public static int bitCount(long i) {// HD, Figure 5-14i = i - ((i >>> 1) & 0x5555555555555555L);i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;i = i + (i >>> 8);i = i + (i >>> 16);i = i + (i >>> 32);return (int)i & 0x7f; } 這個方法是返回一個long類型的數(shù)字對應(yīng)的二進制中1的個數(shù)，其實google上有很多種，這里采用的叫平行算法實現(xiàn)的，算法如下圖。

但是這個方法的第一行又采取了一個特別的方式實現(xiàn)i中奇數(shù)位+偶數(shù)位，我有點兒沒想明白。總體上就是像圖中所示那樣，相鄰的兩位相加的結(jié)果再相鄰的四位相加，最后得到二進制中1的個數(shù)。 還有一點值得提一下，就是最后一行與上7f，因為long類型，1的個數(shù)最多也不會超過64個，所以只取最后7位即可。

轉(zhuǎn)載于:https://my.oschina.net/u/3647620/blog/1552442

總結(jié)

以上是生活随笔為你收集整理的java java.lang.Long详解之三 大显神通的位移运算的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。