6
\$\begingroup\$

I need to only take first 12 bits of a number if its longer than a 12 bit number and convert it to a decimal number. So if 7000 is entered than it will return 3500. I also print out the binary form of the new number to check if its converting and far as I can tell it is.

I am wondering if there is a better way to write this code?

#include <iostream>
#include <sstream>
#include <string>
#include <stack> 
using namespace std;


int main()
{
    int num, total = 0, x = 0, sizeOfStack, foo[12], i = 0;
    stack <int>  s; // You need the stack;
    stringstream ss;
    unsigned long long int binaryNumber;

    cout << "Please enter a decimal: ";
    cin >> num;

    while (num > 0)
    {
        total = num % 2;
        num /= 2;
        s.push(total); // push 'total'(?) onto the stack
                       //cout << total;
    }
    sizeOfStack = s.size();
    while (x < 12 && x < sizeOfStack) // Another loop to get the values from the stack / now in the correct order
    {
        if (!s.empty())
        {
            foo[i] = s.top();
            s.pop();
        }
        x++; // increment while loop
        i++; //increment array

    }
    for (int w : foo)
    {
        ss << w; // Converting an Integer Array into a Number 
    }
    string some = ss.str();
    const char *p = some.c_str();
    binaryNumber = strtoull(p, NULL, 10);
    cout << "The Binary Number is: " << binaryNumber << endl;
    unsigned long long int  dec = 0, rem, num2, base = 1;
    num2 = binaryNumber; //set binarynum2ber to num2
    while (num2 > 0)
    {
        rem = num2 % 10;
        dec = dec + rem * base;
        base = base * 2;
        num2 = num2 / 10;
    }
    cout << "The Decimal Number is: " << dec << endl;
    cout << endl;
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ The first 12 bits of 7000dec (0001 1011 0101 1000bin) are 0001 1011 0101bin. That's 437dec, not 3500. \$\endgroup\$ – Mast Nov 8 '17 at 15:26
  • \$\begingroup\$ Why not just bitshift? \$\endgroup\$ – Incomputable Nov 8 '17 at 15:30
6
\$\begingroup\$

There is a lot of room for improvement here, but first, let us talk about code style and best practices.

  1. using namespace std; is not a good practice, because it can make your code harder to read if you are using a lot of standard functionality and introduce hard-to-spot name resolution problems. While that is less likely to be an issue in short programs, I still advise you to not use it (creating good habits is worth a lot in the long run!).

  2. Don't do too much on a single line! In particular, don't int num, total = 0, x = 0, sizeOfStack, foo[12], i = 0;, because, on the one hand, you are likely to forget an initializer or a part of a type here and, in the worst case, end up with undefined behavior, and, on the other hand, it is just hard to read for everybody not familiar with your code (such as I). Please split that line up into multiple definitions and declarations. Also, ...

  3. Initialize and use variables as locally as possible. This not only prevents scope pollution, but also increases the readability of your code. As a reviewer, I don't want to (and even cannot) keep a mental map on more than a handful of variables, especially if I have to remember them through large blocks of code where they don't even appear once.

  4. To my understanding at least, the term decimal implies floating point numbers, not just integers. Please think about clarifying, e.g. by writing "decimal integers" or something alike.

  5. Your code does (probably) unexpected thing for numbers smaller than 0. Since you take input as an int and also do virtually no error checking, you could end up with the user inputting a negative number, for which your code will output 0 for the binary and 0 for the decimal representation. If you don't want to accept negative numbers at all, num should be unsigned. If you do, change your implementation to work correctly for those. Either way, you should do input verification on the numbers (or non-numbers) you get.

  6. Don't use std::endl. If you want a newline, simply write '\n'. The reason is that std::endl does more than the name suggests. In particular it writes a '\n' and flushes the underlying buffer which is very rarely what you want or need to do because it seldom yields any benefits and can decrease performance.

  7. Order your includes. In general, alphabetic ordering is expected to enable fast header verification for people reading your code.

  8. Write meaningful comments. In particular, follow the DRY principle in comments as well as code, which means that s.push(total); // push 'total'(?) onto the stack, for example, should go without the comment because it only repeats what the code does. Instead, try to us comments to give reasons as to why you're doing something, and don't overuse them because you've read somewhere that "the more comments, the better". Usefulness and clarity are key.

  9. foo is not exactly what I would call a good variable name. Most of your other names are good, but this one identifier is definitely not. How about something along the lines of binaryDigits instead?

  10. If you have access to anything >=C++11, use nullptr in place of NULL because NULL is fragile and convertible to a lot of things that are not actually pointers.


You asked

I am wondering if there is a better way to write this code?

and the answer to that is yes. The main idea of your current implementation is to use a stack with your numbers binary digits, which is wasteful (and probably slow) in comparison to just doing the operation in place using bitshifting.

The algorithm that I would propose works like this:

1. Find the highest set bit (= most significant set bit/mssb) in the input
2. Shift the number right so that the mssb is in 12th position

which should be simple enough to implement. Let's walk this through step by step:

  1. There are different algorithms for finding the most significant bit, but usually an iterative approach works well enough. The general idea is to iterate the number bitwise from the most significant to the least significant bit, checking whether the current bit is set. If it is, return the current bit position. In code, this might look like this:

    static unsigned find_mssb(unsigned const num) {
    
        unsigned const num_bit_count = sizeof num * CHAR_BIT;
    
        unsigned flag = 1u << (num_bit_count - 1u);
    
        //num_bit_count is also the index of the msb
        unsigned index = num_bit_count;
        while (index) {
    
            if (num & flag) {
                return index;
            }
    
            flag >>= 1u;
            --index;
        }
    
        return 0u;
    }
    

    It is important to note that the least significant byte has the index 1, not 0, because we reserve 0 for the occasion that no bit is actually set. Alternatively, if you use either gcc or clang, there is the builtin __builtin_clz which returns the number of leading zeroes, greatly simplifying the computation:

    static unsigned find_mssb(unsigned const num) {
    
        unsigned const num_bit_count = sizeof num * CHAR_BIT;
    
        //__builtin_clz(0u) is undefined behavior
        if (num) {
            unsigned leading_zeroes = __builtin_clz(num);
            return num_bit_count - leading_zeroes;
        }
    
        return 0u;
    }
    

    Now that we have a way to find the most significant set bit, let's move on to step

  2. Shifting the number right so that the most significant set bit is in the 12th position. This is trivial to do. In code:

    unsigned mssb = find_mssb(number);
    
    if (mssb < 12u) {
      //error message, exit, ...
    }
    
    number >>= mssb - 12u;
    

    And we're done.

Putting all of this (and some bits of supporting code) together, a reworked version of your program could look something like this:

#include <algorithm>
#include <climits>
#include <iostream>
#include <limits>
#include <sstream>

static unsigned find_mssb(unsigned const num) {

    unsigned const num_bit_count = sizeof num * CHAR_BIT;

#ifdef __GNUG__

    if (num) {
        unsigned leading_zeroes = __builtin_clz(num);
        return num_bit_count - leading_zeroes;
    }

#else
    unsigned flag = 1u << (num_bit_count - 1);

    unsigned index = num_bit_count;
    while (index) {

        if (num & flag) {
            return index;
        }

        flag >>= 1;
        --index;
    }

#endif

    return 0;
}

static std::string binary_representation(unsigned num) {

    std::ostringstream representation;

    while (num) {
        representation << (num & 0x1u);
        num >>= 1;
    }

    std::string str {representation.str()};
    std::reverse(str.begin(), str.end());

    return str;
}

int main() {

    std::cout << "Please enter an integer\n> ";
    unsigned number;
    std::cin >> number;

    unsigned mssb = find_mssb(number);

    if (mssb < 12u) {
        std::cout << "The number you entered is too short. Its binary"
            " representation is only " << mssb << " bits long, which is"
            " less than the required length of 12. In binary, your number is "
            << binary_representation(number) << ".\n";
        return 0;
    }

    number >>= mssb - 12u;
    std::cout << "The trimmed number is "<< number
            << ". The 12 most significant bits are "
            << binary_representation(number) << '\n';
}

Edit: As TobySpeight mentioned in the comments, the bit length of char is not dictated by the standard, so assuming each byte has eight bits is not portable. Instead, the standard library offers CHAR_BIT instead, which is now used in the updated code.

\$\endgroup\$
  • \$\begingroup\$ Is sizeof num * 8 a misspelling of sizeof num * CHAR_BIT? If so, you'll need to include <climits> when you correct it. \$\endgroup\$ – Toby Speight Nov 9 '17 at 9:13
  • \$\begingroup\$ A simpler alternative to std::reverse(str.begin(), str.end()); return str; could be return {str.rbegin(), str.rend()}; \$\endgroup\$ – Toby Speight Nov 9 '17 at 9:16
  • \$\begingroup\$ @TobySpeight You're right, of course. I just forgot about the fact that the bit size of char is not fixed by the standard. \$\endgroup\$ – Ben Steffan Nov 9 '17 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.