在實際編程中，按位操作是否通用且有用？

我經常遇到涉及排序/未排序數組的面試問題，他們要求您查找此數組的某種屬性。例如finding the number that appears odd number of times in an array或find the missing number in an unsorted array of size one million。通常這個問題需要額外的約束，比如O（n）運行時複雜度，或者O（1）空間複雜度。這兩個問題都可以通過按位操作相當有效地解決。當然，這些並不是全部，有很多這樣的問題。在實際編程中，按位操作是否通用且有用？

對我來說，按位編程似乎更像是基於黑客或直覺，因爲它工作在二進制而非小數。作爲一名沒有太多現實生活編程經驗的大學生，我很好奇這種類型的問題在實際工作中是否真正受到歡迎，還是他們只是面試官用來挑選最聰明的候選人的腦筋急轉彎。如果它們確實有用，它們實際上適用於哪種場景？

來源

2013-04-09 turtlesoup

指定二進制選項（例如打開/關閉選項）是首先想到的。 – nhahtdh 2013-04-09 01:25:31

@nhahtdh具體來說，XOR是迄今爲止我見過的最受歡迎的二元運算符，我不明白他們爲什麼總是在解決問題時很方便 – turtlesoup 2013-04-09 01:29:43

如果您正在研究一個算法的實現或實現一些庫，那麼你會看到位運算符相當多。如果你的工作水平超出了這個範圍（重用圖書館），那就不那麼重要了。 – nhahtdh 2013-04-09 01:31:14

從我的經驗來看，當您爲大數據集提高速度和效率時，它非常有用。

爲了表示非常大的集合，我使用了很多位向量，這使得存儲非常高效，並且非常快速地進行比較和組合等操作。我還發現，位矩陣由於相同的原因非常有用，例如找到大量大二進制矩陣的交點。使用二進制掩碼來指定子集也是非常有用的，例如Matlab和Python的Numpy/Scipy使用二進制掩碼（本質上是二進制矩陣）來從矩陣中選擇元素的子集。

來源

2013-04-09 01:28:50 Bitwise

使用按位操作嚴格取決於您的主要問題。

我曾經要求解決問題，以找到號碼哪些沒有

具有在其中重複的數字，這是形式的N個的所有組合* 1，對於給定的我。

我突然利用位操作，併產生所有的數字正好與更好

時間，但讓我吃驚，我被要求重寫和代碼與沒有使用按位

運營商，如人們發現沒有可讀性，許多人必須使用的代碼

進一步。所以，如果性能是你關心的Bitwise。

如果可讀性是您關心的問題，請減少它們的使用。

如果你在時間要兩個，你需要遵循編寫代碼的好作風按位

運營商在某種程度上，它是可讀或理解的。

來源

2013-04-09 07:44:50 MissingNumber

儘管如果你真的不關心它，你通常可以在用戶級代碼中「避免它」，但它對於內存消耗是一個大問題的情況會很有用。位操作通常是需要的，甚至在處理硬件設備或嵌入式編程時甚至是需要的。

I/O寄存器通常具有多種不同的配置選項，可通過各種標誌型位組合進行尋址。或者對於內存相對於現代PC RAM大小受到極大限制的小型嵌入式設備，您可能會習慣於正常工作。

它也是在炎熱的代碼中的一些優化，要使用一個免費的分支實施的東西，可以使用條件代碼來表示很方便，但需要更快的運行時性能。例如，在某些處理器上使用比較常見的解決方案的比特攻擊可以非常有效地實現給定整數的2的最近冪。

有一個名爲「黑客的喜悅」亨利·沃倫小大書，充滿了非常有用的功能，適用於各種發生在「現實世界」的代碼問題。還有一些類似的東西在線文件。

從在被稱爲HAKMEM 20世紀70年代MIT人工智能實驗室一位著名的文獻是另一個例子。

來源

2013-04-09 08:27:08

是位運算常見的和有用的在現實生活中的編程？

共性或適用性取決於手頭的問題。

一些現實生活中的項目確實從按位操作中受益。

一些例子：

你在屏幕上直接操縱視頻存儲器，其中每一個像素的顏色是由1或4位表示設置單個像素。因此，在每個字節中，您可以打包8或2個像素，並且需要將它們分開。基本上，您的硬件決定使用按位操作。
您正在處理某種文件格式（例如GIF）或網絡協議，它使用個別位或位組來表示信息片段。您的數據決定使用按位操作。
則需要通過與位操作來計算某種checksum（可能parity或CRC）或hash value和一些最適用的算法做到這一點。
你實現（或使用）的arbitrary-precision arithmetic庫。
您正在實施FFT，您自然需要reverse bits in an integer或在添加時模擬相反方向的進位傳播。算法的本質需要一些按位操作。
您的空間不足，需要使用盡可能少的內存，並將多個位值和位組壓入多個字節，字，雙字和四字。您選擇使用按位操作來節省空間。
CPU上的分支機構/跳轉代價高昂，您希望通過將代碼作爲一系列指令實施而不需要任何分支機構和按位指令來提高性能。這裏最簡單的例子是選擇兩個中的最小（或最大）整數值。實現它的最自然的方式是使用某種if聲明，最終涉及比較和分支。您選擇使用按位操作來提高速度。
您的CPU支持浮點運算，但計算諸如平方根之類的操作是一種緩慢的操作，您改爲simulate it using a few fast and simple integer and floating operations。同樣，在這裏，您可以通過使用浮點格式的位表示來操作。
您正在模擬一個CPU或整個計算機，並且在解碼指令時，訪問CPU或硬件寄存器的某些部分時，需要處理個別位（或位組），只需模擬按位指令，如OR ，AND,XOR,NOT等等。您的問題不再需要按位指示。
您正在解釋按位智能的算法或技巧，或者需要按位操作給網絡上其他人（例如此處）或書中的內容。 :)

我在過去的20年裏親自完成了以上所有工作。 YMMV，但。

來源

2013-04-09 08:47:27

FWIW，＃6通常在將多個複選框值從網頁存儲到單個int32數據庫字段中時發揮作用... – 2013-04-09 18:04:50

在實際編程中，按位操作是否通用且有用？

回答

相關問題