Last active
November 2, 2016 11:16
-
-
Save pceccato/6a6f96b21bcf750703e8cc7f34429b17 to your computer and use it in GitHub Desktop.
a class for computing the n-bit sequences with no adjacent 1's. A going test. Run it here: http://ideone.com/aqMQ5w
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <string> | |
| // | |
| // a class for computing the n-bit sequences with no adjacent 1's | |
| // | |
| // Approach taken was to search the entire solution space for all n-bit | |
| // sequences that satisfy the criteria | |
| // An small optimization was made to prune the solution space by not checking | |
| // the lower bits of a sequence if | |
| // an adjacent pair of 1's is found in the higher bits. | |
| // | |
| // PAC 7/10/2015 | |
| // | |
| class NBitSequenceTest | |
| { | |
| public: | |
| // | |
| // constructor takes the number of bits in the sequence | |
| // | |
| NBitSequenceTest(unsigned int n); | |
| // | |
| // outputs all n bit sequences with no consecutive 1's to standard output. | |
| // returns the number of sequences found. | |
| // | |
| unsigned int Evaluate() const; | |
| private: | |
| // | |
| // returns the position of the least significant bit of the pair of | |
| // adjacent 1's in the number. returns -1 if there are no adjacent 1s | |
| // in the bit pattern. | |
| // | |
| int hasAdjacentBitSetAtPosition(unsigned int number) const; | |
| // | |
| // helper function for numberToBinaryString tests if a bit at a certain position is set. | |
| // | |
| bool isBitSet(unsigned int number, unsigned int nBit) const; | |
| // | |
| // outputs the input number as a string in binary format | |
| // | |
| std::string numberToBinaryString(unsigned int number) const; | |
| // | |
| // store the number of bits in the sequence | |
| // | |
| unsigned int m_nDigits; | |
| }; | |
| inline bool NBitSequenceTest::isBitSet(unsigned int number, unsigned int nBit) const | |
| { | |
| return (number & 1 << nBit) != 0; | |
| } | |
| NBitSequenceTest::NBitSequenceTest(unsigned int n) : m_nDigits(n) | |
| {} | |
| std::string NBitSequenceTest::numberToBinaryString(unsigned int number) const | |
| { | |
| std::string strBinary(m_nDigits, '0'); | |
| int bitPos = 0; | |
| for (std::string::reverse_iterator i = strBinary.rbegin(); i != strBinary.rend(); i++) | |
| { | |
| if (isBitSet(number,bitPos++)) | |
| *i = '1'; | |
| } | |
| return strBinary; | |
| } | |
| int NBitSequenceTest::hasAdjacentBitSetAtPosition(unsigned int number) const | |
| { | |
| // | |
| // our minimum condition is 2 adjacent bits set, | |
| // so our test will loop through the bits looking for this pattern | |
| // | |
| const unsigned int twoBits = 1 | 1 << 1; | |
| int pos = -1; | |
| bool bStopChecking = false; | |
| for (unsigned int i = 0; i < (m_nDigits - 1) && !bStopChecking; i++) | |
| { | |
| unsigned int currentMask = twoBits << i; | |
| if ((number & currentMask) == currentMask) | |
| { | |
| pos = i; | |
| bStopChecking = true; | |
| } | |
| else if (number < currentMask) | |
| { | |
| // | |
| // no point chekcing any further as the bits will all be zero | |
| // | |
| bStopChecking = true; | |
| } | |
| } | |
| return pos; | |
| } | |
| unsigned int NBitSequenceTest::Evaluate() const | |
| { | |
| const unsigned int upperBound = (1 << m_nDigits); | |
| unsigned int i = 0; | |
| unsigned int count = 0; | |
| do | |
| { | |
| int posBitPair = hasAdjacentBitSetAtPosition(i); | |
| if (posBitPair < 0) | |
| { | |
| std::cout << numberToBinaryString(i++) << std::endl; | |
| count++; | |
| } | |
| else | |
| { | |
| // | |
| // optimization... if we found a pair of adjacent bits they will remain set | |
| // until the lsb of the bit pair flips back to zero when the remaining lower | |
| // significant bits overflow and reset | |
| // back to all zeros. so we can skip these candidates | |
| // | |
| i += (1 << posBitPair); | |
| } | |
| } while (i < upperBound); | |
| return count; | |
| } | |
| int main() { | |
| int n; | |
| std::cin >> n; | |
| NBitSequenceTest b(n); | |
| std::cout << b.Evaluate() << " results found" << std::endl; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment