我正在為以下問題尋找偽代碼或 java 或 js 的解決方案：我們需要實現一個有效的位結構來保存 N 位的數據（您也可以將這些位視為布爾值，開/關）。我們需要支持以下方法： init(n) get(index) set(index, True/False) setAll(True/false)現在我得到了一個包含 o(1) 的解決方案，除了 init 是 o(n)。這個想法是創建一個數組，其中每個索引都保存一點值。為了支持 setAll，我還將使用位 vapue 保存時間戳，以了解是從 tge 數組中獲取值還是從 tge 最后一個 setAll 值中獲取值。init 中的 o(n) 是因為我們需要遍歷數組來將它清零，否則它會產生垃圾，可以是任何東西?，F在我被要求找到一個 init 也是 o(1) 的解決方案（我們可以創建一個數組，但我們不能清除垃圾，垃圾甚至可能看起來像有效的數據，這是錯誤的并使解決方案變得糟糕，我們需要100% 有效的解決方案）。更新：這是一個算法問題，而不是特定于語言的問題。我在面試問題中遇到過。由于內存限制，使用整數來表示位數組也不夠好。我被告知它與對數組中的垃圾數據進行某種智能處理有關，而無需在 init 中對其進行處理，使用某種機制不落下，因為如果數組中的垃圾數據（但我不是確定如何）。
2 回答
慕田峪4524236
TA貢獻1875條經驗 獲得超5個贊
使用 32 位值（8、16、64 個整數也適用）作為存儲和輔助字段，基于 hashmap制作惰性數據結構（而 hashmap 有時可能比 o(1) 的訪問時間更短）InitFlag
要清除所有內容，請制作空地圖InitFlag = 0 （刪除舊地圖是 GC 在 Java 中的工作，不是嗎？）
要設置所有，請制作空地圖 InitFlag = 1
更改某個位時，檢查是否bitnum/32存在對應的 int 鍵。如果是，只需更改bitnum&32位，如果不是，則位值不同于InitFlag- 創建具有基于InitFlag（全零或全一）的值的鍵并更改所需的位。
在檢索某個位時，檢查是否存在對應的密鑰。如果是，則提取位，如果不是 - 獲取InitFlag值
SetAll(0): ifl = 0, map - {}
SetBit(35): ifl = 0, map - {1 : 0x10}
SetBit(32): ifl = 0, map - {1 : 0x12}
ClearBit(32): ifl = 0, map - {1 : 0x10}
ClearBit(1): do nothing, ifl = 0, map - {1 : 0x10}
GetBit(1): key=0 doesn't exist, return ifl=0
GetBit(35): key=1 exists, return map[1]>>3 =1
SetAll(1): ifl = 1, map = {}
SetBit(35): do nothing
ClearBit(35): ifl = 1, map - {1 : 0xFFFFFFF7 = 0b...11110111}
and so on
一只萌萌小番薯
TA貢獻1795條經驗 獲得超7個贊
如果這是大學/高中計算機科學測試或家庭作業問題 - 我懷疑他們試圖讓您使用BOOLEAN BIT-WISE LOGIC - 具體來說，將位保存在 int 或 long 中。我懷疑（但我不是讀心者——我可能是錯的?。┦褂谩皵到M”正是你的老師希望你避免的。
例如 - 這句話是從谷歌的搜索結果中復制的：
長：將長的數據類型是一個64位的二的補碼整數。有符號 long 的最小值為 -263，最大值為 263-1。在 Java SE 8 及更高版本中，您可以使用 long 數據類型來表示無符號的 64 位 long，其最小值為 0，最大值為 264-1
這意味著 Java 中的單個 long 變量可以存儲 64 個按位值：
long storage;
// To get the first bit-value, use logical-or ('|') and get the bit.
boolean result1 = (boolean) storage | 0b00000001; // Gets the first bit in 'storage'
boolean result2 = (boolean) storage | 0b00000010; // Gets the second
boolean result3 = (boolean) storage | 0b00000100; // Gets the third
...
boolean result8 = (boolean) storage | 0b10000000; // Gets the eighth result.
我可以為您編寫整個內容，但我不能 100% 確定您的實際規格 - 如果您使用 long，則只能存儲 64 個單獨的二進制值。如果您想要任意數量的值，則必須根據需要使用盡可能多的“長”。
這是關于二進制/布爾值的 SO 帖子： Java 中的二進制表示
這是一篇關于位移位的 SO 帖子： Java - Circular shift using bitwise operations
同樣，這將是一份工作，我不會編寫整個項目。但是，get(int index)和set(int index, boolean val)方法將涉及數字 1 的逐位移位。
int pos = 1;
pos = pos << 5; // This would function as a 'pointer' to the fifth element of the binary number list.
storage | pos; // This retrieves the value stored as position 5.
添加回答
舉報
0/150
提交
取消