[問題] byte 值 -1 如何右移位元一位成為 127

看板java作者bleed1979 (十三)時間10年前 (2014/10/26 17:51)推噓2(2推 0噓 6→)

留言8則, 5人參與討論串1/1

byte i = -1; System.out.println(寫在這裡); 輸出為127，在禁止左移運算手動清除bit 7的情況下，how? 謝謝。 ======================= 編輯分隔線 =========================== 目前推文仍沒有完善的方法。理由我想還是把故事交代一下。此刻我的電腦正在跑 33 Queens puzzle，只需求出一個正確解。 33 Queens 的題目為 8 Queens 的延伸，多一個條件且只需求一個正確解。但姑且不論多出條件的內容為何，僅討論資料結構。由於 8 Queens 的 8 在一個 int 的位元數之內，所以很容易以位元運算來加速求解。比如：以 left 變數代表左移一位的遮罩， center 變數代表中路的遮罩， right 變數代表右移一位的遮罩，以 b 變數代表此列皇后擺放後已經設立起唯一一個bit的值。 4者皆為 int 變數。於是乎 ((left | b) << 1) | (center | b) | ((right | b) >> 1) 傳進入recursion，就是下一列皇后不可擺放的遮罩。現在問題就出現在 ((right | b) >> 1) 的 >> 1 上面，在不使用long資結情況下 ... 註：其實題目N Queens最高不超過1000，看你能給出最高多少的一個正確解。我先取 N 為 13，並使用資結為 byte[] 的方式，以array展開我所需要的 right 變數，並定義了一個 class Row { private int n; private int sz; private byte[] ary; } 其中的一個shiftRight() method，代表右移一位的 method，所以我只要 public Row shiftRight() { Row row = new Row(n); byte[] rowAry = row.getAry(); boolean carry = false; // 是否跨過邊界的借位 for(int i = sz - 1; i >= 0; --i) { rowAry[i] = ary[i] 右移一位並 or ((carry?1:0) << 7); if((ary[i] & 1) != 0) { carry = true; } else { carry = false; } } ... 一些處理 ... return row; } 上述 ary 是原本沒右移的值，這個method會回傳一個新的row。我必須解決的是把上面"右移一位"寫成程式。由於 bits 運算的 domain 是在 int 層次以上的， byte 去移位 >> 或 >>> 得出的型別是 int，於是乎使用 >>> 原本可以達到目的，但碰到 byte 得出的卻會是 byte i = -1; i >>> 1 會是 2147483647，強轉 byte 會變成 -1。我是可以將 byte [] 改成 int [] 然後使用 >>> 但跨邊界是 33 起跳，對於 NP-Complete 的題目，在不確定改code一定是對的情況下，不這麼貿然行事。(會很久，沒騙你) 目前以 byte[] 來做跑 13 跨界的確定答案為正確。上述右移一位的code我是以手動清除來做。 ((ary[i] >> 1) & ~(1 << 7)) | ((carry?1:0) << 7); 但多一個運算即使是 bits 運算，還是會推慢速度，故 po 文尋求解法。感謝提供解法的板友，在我跑完 byte[] 後，改 int []，這問題就不復存在。不過還是好奇能否有完善的改法，謝謝。 2014/10/26 22:20 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.203.156 ※ 文章網址: http://www.ptt.cc/bbs/java/M.1414317110.A.7E4.html