C++
बिट मैनिपुलेशन
खोज…
टिप्पणियों
std::bitset का उपयोग करने के लिए आपको <bitset> हेडर शामिल करना होगा।
#include <bitset>
std::bitset , ऑपरेटर के सभी कार्यों को ओवरलोड करता है जो बिटसेट्स के सी-स्टाइल हैंडलिंग के समान उपयोग की अनुमति देता है।
संदर्भ
थोडा सेटिंग करना
सी-स्टाइल बिट हेरफेर
बिटवाइज़ या ऑपरेटर ( | ) का उपयोग करके एक बिट सेट किया जा सकता है।
// Bit x will be set
number |= 1LL << x;
एसटीडी :: बिटसेट का उपयोग करना
set(x) या set(x,true) - स्थिति x से 1 पर बिट सेट करता है।
std::bitset<5> num(std::string("01100"));
num.set(0); // num is now 01101
num.set(2); // num is still 01101
num.set(4,true); // num is now 11110
थोडा क्लियर करना
सी-स्टाइल बिट-हेरफेर
बिट वाइज और ऑपरेटर ( & ) का उपयोग करके थोड़ा सा साफ किया जा सकता है।
// Bit x will be cleared
number &= ~(1LL << x);
एसटीडी :: बिटसेट का उपयोग करना
reset(x) या set(x,false) - स्थिति x पर बिट को साफ करता है।
std::bitset<5> num(std::string("01100"));
num.reset(2); // num is now 01000
num.reset(0); // num is still 01000
num.set(3,false); // num is now 00000
थोड़ा टॉगल करना
सी-स्टाइल बिट-हेरफेर
XOR ऑपरेटर ( ^ ) का उपयोग करके एक बिट को टॉगल किया जा सकता है।
// Bit x will be the opposite value of what it is currently
number ^= 1LL << x;
एसटीडी :: बिटसेट का उपयोग करना
std::bitset<4> num(std::string("0100"));
num.flip(2); // num is now 0000
num.flip(0); // num is now 0001
num.flip(); // num is now 1110 (flips all bits)
थोड़ा जाँच कर रहा है
सी-स्टाइल बिट-हेरफेर
बिट का मान संख्या को सही x बार शिफ्ट करके और फिर उस पर बिटवाइज़ और ( & ) प्रदर्शन करके प्राप्त किया जा सकता है:
(number >> x) & 1LL; // 1 if the 'x'th bit of 'number' is set, 0 otherwise
राइट-शिफ्ट ऑपरेशन को अंकगणित (हस्ताक्षरित) शिफ्ट या तार्किक (अहस्ताक्षरित) शिफ्ट के रूप में लागू किया जा सकता है। यदि number में अभिव्यक्ति number >> x एक हस्ताक्षरित प्रकार और एक नकारात्मक मूल्य होता है, जिसके परिणामस्वरूप मूल्य कार्यान्वयन परिभाषित किया गया है।
अगर हमें सीधे उस जगह के मूल्य की आवश्यकता है, तो हम बदले में मास्क को छोड़ सकते हैं:
(number & (1LL << x)); // (1 << x) if the 'x'th bit of 'number' is set, 0 otherwise
या तो एक सशर्त के रूप में इस्तेमाल किया जा सकता है, क्योंकि सभी गैर-शून्य मानों को सच माना जाता है।
एसटीडी :: बिटसेट का उपयोग करना
std::bitset<4> num(std::string("0010"));
bool bit_val = num.test(1); // bit_val value is set to true;
Nth बिट को x में बदलना
सी-स्टाइल बिट-हेरफेर
// Bit n will be set if x is 1 and cleared if x is 0.
number ^= (-x ^ number) & (1LL << n);
एसटीडी :: बिटसेट का उपयोग करना
set(n,val) - सेट थोड़ा n मूल्य के लिए val ।
std::bitset<5> num(std::string("00100"));
num.set(0,true); // num is now 00101
num.set(2,false); // num is now 00001
सभी बिट्स सेट करें
सी-स्टाइल बिट-हेरफेर
x = -1; // -1 == 1111 1111 ... 1111b
(यह क्यों काम करता है और वास्तव में सबसे अच्छा तरीका है की व्याख्या के लिए यहां देखें।)
एसटीडी :: बिटसेट का उपयोग करना
std::bitset<10> x;
x.set(); // Sets all bits to '1'
सबसे सही सेट बिट निकालें
सी-स्टाइल बिट-हेरफेर
template <typename T>
T rightmostSetBitRemoved(T n)
{
// static_assert(std::is_integral<T>::value && !std::is_signed<T>::value, "type should be unsigned"); // For c++11 and later
return n & (n - 1);
}
व्याख्या
- यदि
nशून्य है, तो हमारे पास0 & 0xFF..FFजो शून्य है - और
nको0bxxxxxx10..00औरn - 1को0bxxxxxx011..11लिखा जा सकता है, इसलिएn & (n - 1)0bxxxxxx000..00।
गिनती के बिट सेट
एक बिटस्ट्रिंग की जनसंख्या गणना की आवश्यकता अक्सर क्रिप्टोग्राफी और अन्य अनुप्रयोगों में होती है और समस्या का व्यापक रूप से अध्ययन किया गया है।
भोली को प्रति बिट एक पुनरावृत्ति की आवश्यकता होती है:
unsigned value = 1234;
unsigned bits = 0; // accumulates the total number of bits set in `n`
for (bits = 0; value; value >>= 1)
bits += value & 1;
एक अच्छी ट्रिक ( राइट राइट सेट बिट पर आधारित) है:
unsigned bits = 0; // accumulates the total number of bits set in `n`
for (; value; ++bits)
value &= value - 1;
यह कई पुनरावृत्तियों से गुजरता है क्योंकि वहाँ सेट बिट्स होते हैं, इसलिए यह अच्छा है जब value में कुछ नॉनजरो बिट्स होने की उम्मीद है।
विधि पहले पीटर वेगनर ( सीएसीएम 3/322 - 1960 में) द्वारा प्रस्तावित की गई थी और यह अच्छी तरह से ज्ञात है क्योंकि यह सी प्रोग्रामिंग भाषा में ब्रायन डब्ल्यू केर्निघन और डेनिस एम। रिची द्वारा प्रकट होता है।
इसके लिए 12 अंकगणितीय परिचालनों की आवश्यकता होती है, जिनमें से एक बहुक्रिया है:
unsigned popcount(std::uint64_t x)
{
const std::uint64_t m1 = 0x5555555555555555; // binary: 0101...
const std::uint64_t m2 = 0x3333333333333333; // binary: 00110011..
const std::uint64_t m4 = 0x0f0f0f0f0f0f0f0f; // binary: 0000111100001111
x -= (x >> 1) & m1; // put count of each 2 bits into those 2 bits
x = (x & m2) + ((x >> 2) & m2); // put count of each 4 bits into those 4 bits
x = (x + (x >> 4)) & m4; // put count of each 8 bits into those 8 bits
return (x * h01) >> 56; // left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
}
इस तरह के कार्यान्वयन में सबसे खराब स्थिति वाला व्यवहार होता है (आगे के विवरण के लिए हेमिंग वजन देखें)।
कई सीपीयू में एक विशिष्ट निर्देश होता है (जैसे x86 का popcnt ) और संकलक एक विशिष्ट ( गैर मानक ) फ़ंक्शन में निर्मित की पेशकश कर सकता है। जैसे जी ++ के साथ है:
int __builtin_popcount (unsigned x);
जांचें कि क्या पूर्णांक 2 की शक्ति है
n & (n - 1) ट्रिक (देखें सबसे दाहिना सेट बिट निकालें ) यह निर्धारित करने के लिए भी उपयोगी है कि क्या पूर्णांक 2 की शक्ति है:
bool power_of_2 = n && !(n & (n - 1));
ध्यान दें कि चेक के पहले भाग के बिना ( n && ), 0 को गलत तरीके से 2 की शक्ति माना जाता है।
बिट मैनीपुलेशन एप्लिकेशन: कैपिटल लेटर के लिए छोटा
बिट हेरफेर के कई अनुप्रयोगों में से एक एक मुखौटा और एक उचित बिट ऑपरेशन का चयन करके छोटे से पूंजी या इसके विपरीत से एक पत्र परिवर्तित कर रहा है। उदाहरण के लिए, एक पत्र में यह द्विआधारी प्रतिनिधित्व 01(1)00001 जबकि इसके पूंजी समकक्ष के पास 01(0)00001 । वे पूरी तरह से कोष्ठक में थोड़ा भिन्न होते हैं। इस मामले में, एक पत्र को छोटी से पूंजी में परिवर्तित करना मूल रूप से कोष्ठक में बिट को एक में सेट करना है। ऐसा करने के लिए, हम निम्नलिखित कार्य करते हैं:
/****************************************
convert small letter to captial letter.
========================================
a: 01100001
mask: 11011111 <-- (0xDF) 11(0)11111
:---------
a&mask: 01000001 <-- A letter
*****************************************/
पत्र को A अक्षर में परिवर्तित करने का कोड है
#include <cstdio>
int main()
{
char op1 = 'a'; // "a" letter (i.e. small case)
int mask = 0xDF; // choosing a proper mask
printf("a (AND) mask = A\n");
printf("%c & 0xDF = %c\n", op1, op1 & mask);
return 0;
}
परिणाम है
$ g++ main.cpp -o test1
$ ./test1
a (AND) mask = A
a & 0xDF = A