ExtensiveBitRegister.h

Go to the documentation of this file.

/* Copyright 2016 Kristofer Björnson
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
 
#ifndef COM_DAFER45_TBTK_EXTENSIVE_BIT_REGISTER
#define COM_DAFER45_TBTK_EXTENSIVE_BIT_REGISTER
 
#include "TBTK/Streams.h"
#include "TBTK/TBTKMacros.h"
 
#include <climits>
 
namespace TBTK{
 
class ExtensiveBitRegister{
public:
    ExtensiveBitRegister();
 
    ExtensiveBitRegister(unsigned int numBits);
 
    ExtensiveBitRegister(const ExtensiveBitRegister &extensiveBitRegister);
 
    ~ExtensiveBitRegister();
 
    const ExtensiveBitRegister operator|(
        const ExtensiveBitRegister &rhs
    ) const;
 
    const ExtensiveBitRegister operator&(
        const ExtensiveBitRegister &rhs
    ) const;
 
    const ExtensiveBitRegister operator^(
        const ExtensiveBitRegister &rhs
    ) const;
 
    const ExtensiveBitRegister operator+(
        const ExtensiveBitRegister &rhs
    ) const;
 
    const ExtensiveBitRegister operator-(
        const ExtensiveBitRegister &rhs
    ) const;
 
    bool operator<(const ExtensiveBitRegister &rhs) const;
 
    bool operator>(const ExtensiveBitRegister &rhs) const;
 
    bool operator==(const ExtensiveBitRegister &rhs) const;
 
    void operator+=(const ExtensiveBitRegister &rhs);
 
    void operator-=(const ExtensiveBitRegister &rhs);
 
    const ExtensiveBitRegister& operator++();
 
    const ExtensiveBitRegister operator++(int);
 
    const ExtensiveBitRegister& operator--();
 
    const ExtensiveBitRegister operator--(int);
 
    void operator=(const ExtensiveBitRegister &rhs);
 
    void operator=(const unsigned int rhs);
 
    ExtensiveBitRegister operator<<(unsigned int rhs) const;
 
    ExtensiveBitRegister operator>>(unsigned int rhs) const;
 
    void setBit(unsigned int position, bool values);
 
    bool getBit(unsigned int position) const;
 
    bool toBool() const;
 
    unsigned int toUnsignedInt() const;
 
    void clear();
 
    void print() const;
 
    unsigned int getNumBits() const;
 
    unsigned int getNumOneBits() const;
 
    bool getMostSignificantBit() const;
 
    void setMostSignificantBit();
 
    void clearMostSignificantBit();
 
    ExtensiveBitRegister cloneStructure() const;
 
    std::string toString() const;
 
    friend std::ostream& operator<<(
        std::ostream &stream,
        const ExtensiveBitRegister &extensiveBitRegister
    );
private:
    unsigned int size;
 
    unsigned int *values;
 
    static constexpr unsigned int MOST_SIGNIFICANT_BIT_MASK
        = (unsigned int)0x1 << (8*sizeof(unsigned int) - 1);
};
 
inline const ExtensiveBitRegister ExtensiveBitRegister::operator|(
    const ExtensiveBitRegister &rhs
) const{
    TBTKAssert(
        size == rhs.size,
        "ExtensiveBitRegister::operator|()",
        "Incompatible register sizes.",
        ""
    );
 
    ExtensiveBitRegister result = cloneStructure();
    for(unsigned int n = 0; n < size; n++)
        result.values[n] = values[n] | rhs.values[n];
 
    return result;
}
 
inline const ExtensiveBitRegister ExtensiveBitRegister::operator&(
    const ExtensiveBitRegister &rhs
) const{
    TBTKAssert(
        size == rhs.size,
        "ExtensiveBitRegister::operator|()",
        "Incompatible register sizes.",
        ""
    );
 
    ExtensiveBitRegister result = cloneStructure();
    for(unsigned int n = 0; n < size; n++)
        result.values[n] = values[n] & rhs.values[n];
 
    return result;
}
 
inline const ExtensiveBitRegister ExtensiveBitRegister::operator^(
    const ExtensiveBitRegister &rhs
) const{
    TBTKAssert(
        size == rhs.size,
        "ExtensiveBitRegister::operator|()",
        "Incompatible register sizes.",
        ""
    );
 
    ExtensiveBitRegister result = cloneStructure();
    for(unsigned int n = 0; n < size; n++)
        result.values[n] = values[n] ^ rhs.values[n];
 
    return result;
}
 
inline const ExtensiveBitRegister ExtensiveBitRegister::operator+(
    const ExtensiveBitRegister &rhs
) const{
    TBTKAssert(
        size == rhs.size,
        "ExtensiveBitRegister::operator+()",
        "Incompatible register sizes.",
        ""
    );
 
    ExtensiveBitRegister result = cloneStructure();
    unsigned int carry = 0;
    for(unsigned int n = 0; n < size; n++){
        result.values[n] = values[n] + rhs.values[n];
        unsigned int newCarry = (result.values[n] < values[n]);
        result.values[n] += carry;
        carry = newCarry | (result.values[n] < values[n]);
    }
 
    return result;
}
 
inline const ExtensiveBitRegister ExtensiveBitRegister::operator-(
    const ExtensiveBitRegister &rhs
) const{
    TBTKAssert(
        size == rhs.size,
        "ExtensiveBitRegister::operator+()",
        "Incompatible register sizes.",
        ""
    );
 
    ExtensiveBitRegister result = cloneStructure();
    unsigned int carry = 0;
    for(unsigned int n = 0; n < size; n++){
        result.values[n] = values[n] - rhs.values[n];
        unsigned int newCarry = (result.values[n] > values[n]);
        result.values[n] -= carry;
        carry = newCarry | (result.values[n] > values[n]);
    }
 
    return result;
}
 
inline bool ExtensiveBitRegister::operator<(
    const ExtensiveBitRegister &rhs
) const{
    for(int n = size-1; n >= 0; n--){
        if(values[n] < rhs.values[n])
            return true;
        if(values[n] > rhs.values[n])
            return false;
    }
 
    return false;
}
 
inline bool ExtensiveBitRegister::operator>(
    const ExtensiveBitRegister &rhs
) const{
    for(int n = size-1; n >= 0; n--){
        if(values[n] > rhs.values[n])
            return true;
        if(values[n] < rhs.values[n])
            return false;
    }
 
    return false;
}
 
inline bool ExtensiveBitRegister::operator==(
    const ExtensiveBitRegister &rhs
) const{
    for(unsigned int n = 0; n < size; n++){
        if(values[n] != rhs.values[n])
            return false;
    }
 
    return true;
}
 
inline void ExtensiveBitRegister::operator+=(const ExtensiveBitRegister &rhs){
    TBTKAssert(
        size == rhs.size,
        "ExtensiveBitRegister::operator+=()",
        "Incompatible register sizes.",
        ""
    );
 
    unsigned int carry = 0;
    for(unsigned int n = 0; n < size; n++){
        unsigned int temp = values[n];
        values[n] = temp + rhs.values[n];
        unsigned int newCarry = (values[n] < temp);
        values[n] += carry;
        carry = newCarry | (values[n] < temp);
    }
}
 
inline void ExtensiveBitRegister::operator-=(const ExtensiveBitRegister &rhs){
    TBTKAssert(
        size == rhs.size,
        "ExtensiveBitRegister::operator-=()",
        "Incompatible register sizes.",
        ""
    );
 
    unsigned int carry = 0;
    for(unsigned int n = 0; n < size; n++){
        unsigned int temp = values[n];
        values[n] = temp - rhs.values[n];
        unsigned int newCarry = (values[n] > temp);
        values[n] -= carry;
        carry = newCarry | (values[n] > temp);
    }
}
 
inline const ExtensiveBitRegister& ExtensiveBitRegister::operator++(){
    for(unsigned int n = 0; n < size; n++){
        if(values[n] == UINT_MAX){
            values[n]++;
        }
        else{
            values[n]++;
            break;
        }
    }
 
    return *this;
}
 
inline const ExtensiveBitRegister ExtensiveBitRegister::operator++(int){
    ExtensiveBitRegister returnValue(*this);
    ++(*this);
 
    return returnValue;
}
 
inline const ExtensiveBitRegister& ExtensiveBitRegister::operator--(){
    for(unsigned int n = 0; n < size; n++){
        if(values[n] == 0){
            values[n]--;
        }
        else{
            values[n]--;
            break;
        }
    }
 
    return *this;
}
 
inline const ExtensiveBitRegister ExtensiveBitRegister::operator--(int){
    ExtensiveBitRegister returnValue(*this);
    --(*this);
 
    return returnValue;
}
 
inline void ExtensiveBitRegister::operator=(const ExtensiveBitRegister &rhs){
    if(this != &rhs){
        if(values == nullptr){
            size = rhs.size;
            values = new unsigned int[size];
            for(unsigned int n = 0; n < size; n++)
                values[n] = rhs.values[n];
        }
        else{
            TBTKAssert(
                size == rhs.size,
                "ExtensiveBitRegister::operator=()",
                "Incompatible register sizes.",
                ""
            );
 
            for(unsigned int n = 0; n < size; n++)
                values[n] = rhs.values[n];
        }
    }
}
 
inline void ExtensiveBitRegister::operator=(const unsigned int rhs){
    values[0] = rhs;
    for(unsigned int n = 1; n < size; n++)
        values[n] = 0;
}
 
inline ExtensiveBitRegister ExtensiveBitRegister::operator<<(unsigned int rhs) const{
    ExtensiveBitRegister result(*this);
    if(rhs > 8*sizeof(unsigned int)){
        result = result << (rhs - 8*sizeof(unsigned int));
 
        for(int n = size-1; n > 0; n--)
            result.values[n] = result.values[n-1];
        result.values[0] = 0;
    }
    else if(rhs == 8*sizeof(unsigned int)){
        for(int n = size-1; n > 0; n--)
            result.values[n] = result.values[n-1];
        result.values[0] = 0;
    }
    else if(rhs != 0){
        for(int n = size-1; n >= 0; n--){
            result.values[n] = result.values[n] << rhs;
            if(n > 0)
                result.values[n] |= result.values[n-1] >> (8*sizeof(unsigned int) - rhs);
        }
    }
 
    return result;
}
 
inline ExtensiveBitRegister ExtensiveBitRegister::operator>>(unsigned int rhs) const{
    ExtensiveBitRegister result(*this);
    if(rhs > 8*sizeof(unsigned int)){
        result = result >> (rhs - 8*sizeof(unsigned int));
 
        for(unsigned int n = 0; n < size-1; n++)
            result.values[n] = result.values[n+1];
        result.values[size-1] = 0;
    }
    else if(rhs != 0){
        for(unsigned int n = 0; n < size; n++){
            result.values[n] = result.values[n] >> rhs;
            if(n < size-1)
                result.values[n] |= result.values[n+1] << (8*sizeof(unsigned int) - rhs);
        }
    }
 
    return result;
}
 
inline void ExtensiveBitRegister::print() const{
    for(unsigned int n = size; n > 0; n--){
        for(int c = 8*sizeof(unsigned int)-1; c >= 0; c--)
            Streams::out << (0x1 & (values[n-1] >> c));
        Streams::out << " ";
    }
    Streams::out << "\n";
}
 
inline void ExtensiveBitRegister::setBit(unsigned int position, bool value){
    values[position/(8*sizeof(unsigned int))] &= ~(1 << (position%(8*sizeof(unsigned int))));
    values[position/(8*sizeof(unsigned int))] ^= (value << (position%(8*sizeof(unsigned int))));
}
 
inline bool ExtensiveBitRegister::getBit(unsigned int position) const{
    return (0x1 & (values[position/(8*sizeof(unsigned int))] >> (position%(8*sizeof(unsigned int)))));
}
 
inline bool ExtensiveBitRegister::toBool() const{
    for(unsigned int n = 0; n < size; n++)
        if(values[n])
            return true;
 
    return false;
}
 
inline unsigned int ExtensiveBitRegister::toUnsignedInt() const{
    return values[0];
}
 
inline void ExtensiveBitRegister::clear(){
    for(unsigned int n = 0; n < size; n++)
        values[n] = 0;
}
 
inline unsigned int ExtensiveBitRegister::getNumBits() const{
    return size*8*sizeof(unsigned int);
}
 
inline unsigned int ExtensiveBitRegister::getNumOneBits() const{
    unsigned int numOnes = 0;
    for(unsigned int n = 0; n < size; n++){
        unsigned int x = values[n];
        x = x - ((x >> 1) & 0x55555555);
        x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
        x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
        x = x + (x >> 8);
        x = x + (x >> 16);
        numOnes += (x & 0x0000003F);
    }
 
    return numOnes;
}
 
inline bool ExtensiveBitRegister::getMostSignificantBit() const{
    return values[size-1] & MOST_SIGNIFICANT_BIT_MASK;
}
 
inline void ExtensiveBitRegister::setMostSignificantBit(){
    values[size-1] |= MOST_SIGNIFICANT_BIT_MASK;
}
 
inline void ExtensiveBitRegister::clearMostSignificantBit(){
    values[size-1] &= !MOST_SIGNIFICANT_BIT_MASK;
}
 
inline ExtensiveBitRegister ExtensiveBitRegister::cloneStructure() const{
    return ExtensiveBitRegister(size*8*sizeof(unsigned int));
}
 
inline std::string ExtensiveBitRegister::toString() const{
    std::stringstream stream;
    for(unsigned int n = getNumBits(); n > 0; n--)
        stream << getBit(n - 1);
 
    return stream.str();
}
 
inline std::ostream& operator<<(
    std::ostream &stream,
    const ExtensiveBitRegister &extensiveBitRegister
){
    stream << extensiveBitRegister.toString();
 
    return stream;
}
 
};  //End of namespace TBTK
 
#endif