TransWikia.com

Bitarr class optimization C++

Code Review Asked by starrk on October 27, 2021

I have implemented a bitarr class that does bit manipulations. I would love to know if there is any way to make the code more optimized. Any input would be much appreciated. Thank you! Note: int main() should not be modified.

    #include <iostream>    
    #include <vector>    
    #include <climits>
    #include <cstring>

    template<size_t NumBits>
    class bitarr
    {
    private:
        static const unsigned NumBytes = (NumBits + CHAR_BIT - 1) / CHAR_BIT;//find number of bytes to track least memory footprint
        unsigned char arr[NumBytes];
    public:
        bitarr() { std::memset(arr, 0, sizeof(arr)); } //initialize array to 0

        void set(size_t bit, bool val = true) {
            if (val == true)
            {
                arr[bit / CHAR_BIT] |= (val << bit % CHAR_BIT);//left shift and OR with masked-bit
            }
        }

        bool test(size_t bit) const {
            return arr[bit / CHAR_BIT] & (1U << bit % CHAR_BIT); //left shift and AND with masked-bit
        } 
        const std::string to_string(char c1, char c2)
        {
            std::string str;
            for (unsigned int i = NumBits; i-- > 0;)
                str.push_back(static_cast<char>
                ('0' + test(i)));
            while (str.find("0") != std::string::npos) {
                str.replace(str.find("0"), 1, std::string{ c1 });
            }
            while (str.find("1") != std::string::npos) {
                str.replace(str.find("1"), 1, std::string{ c2 });
            }
            return str;
        } 
        friend std::ostream& operator<<(std::ostream& os, const bitarr& b)
        {
            for (unsigned i = NumBits; i-- > 0; ) 
                os << b.test(i);
            return os << 'n';
        }
    };

    int main()
    {
        try
        {
            bitarr<5> bitarr;
            bitarr.set(1);
            bitarr.set(2);

            const std::string strr = bitarr.to_string('F', 'T');
            std::cout << strr << std::endl;
            if (strr != "FFTTF")
            {
                throw std::runtime_error{ "Conversion failed" };
            }
        }
        catch (const std::exception& exception)
        {
            std::cout << "Conversion failedn";
        }
    }

One Answer

Use size_t consistently

You use both size_t and unsigned for counting. Stick with size_t.

Use default member initialization

You can use default member initialization to ensure arr[] is initialized, without having to call memset():

class bitarr
{
    static const unsigned NumBytes = (NumBits + CHAR_BIT - 1) / CHAR_BIT;
    unsigned char arr[NumBytes] = {};
    ...
};

You can then also remove the constructor completely.

Unnecessary if-statement in set()

You don't need to check whether val is true in set(). If it is false, the body of the if-statement will still do the right thing. While it might look like that would do a lot of work for nothing, the processor might easily mispredict this condition, making it less efficient than not having the if at all.

Make all functions that do not modify arr[] const

You made the function test() const, but to_string() also does not modify the bit array, so you can make that function const as well.

Optimize to_string()

Your function to_string() is very inefficient. The caller provides you with the characters to use for the representation of one and zero bits, but you first ignore that and build a string of '0' and '1', and then replace those characters one by one. Why not build the string directly using c1 and c2? Also, since you know how long the string will be, you should reserve space for all the characters up front.

std::string to_string(char c1, char c2) const
{
    std::string str;
    str.reserve(NumBits);

    for (size_t i = NumBits; i-- > 0;)
        str.push_back(test(i) ? c2 : c1);

    return str;
}

You implementation also has bugs: to_string('0', '1') results in an infinite loop, and to_string('1', '0') always results in a string with all zeroes.

Answered by G. Sliepen on October 27, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP