Competitive mathematics C++ sources

[Durin]

Hi everyone,

I am preparing for a C++ exam which will include tasks like:
How to check if any number is dividable by 16 without using / and % operators.

I am learning about the general c++ capabilities and structure right now, but I cannot find any good sources to practice for the shown task. I can only suggest that it might be in the field of competitive programming as it involves deep knowledge of C++ functionality.

I would be very grateful for any suggestions on sources, books, websites, or general ideas about how to prepare for such tasks.

Thank you very much in advance.

[lastchance]

What do you know about the number 16?

Try writing a few numbers out in binary and see if you can spot a pattern in those divisible by 16.

[jonnin]

Trying to help... this is not a c++ question. This is a math question. C++ may be how you choose to code it, and its going to be just a couple of lines of simple code once you figure it out, but the real issue is finding the 'trick' to problems like this.

I will give you a few random facts..
computers work in binary, which is base 2.
c++ works well with binary, having bit fields, bitset, bitwise operators, boolean support, and so on.
base 16 and base 2 are directly related in both math and when dealing with bits. hex digits as we know them are just bit groupings of 4 bits, so a byte, pick anything.. 0xAB or whatever. A is 10, so 8+2, or 1010. B is 11, or 1011. so AB in binary is 10101011
<< and >> bitwise shift operators multiply by 2 or divide by 2 for each bit shifted. I suspect it is cheating, but you could use this to divide.
division is repeated subtraction just as multiplication is repeated addition. Inefficient, but this could replace / and %
windows calc supports hex and binary and logic in programmer mode. you can find your algorithm using it. Simply set the mode and multiply 16 by 1,2,3,4,5,... until you see something pop out in the binary representation of the values. Do not forget to see if negative numbers do anything weird.
nothing I have said is the answer. They are just things to get you to start thinking about what you have on hand and how you might solve it (I gave you 3 bad ways to solve it, they work but are not the best way). Lastchance gave you the right answer.

[JLBorges]

> How to check if any number is dividable by 16 without using / and % operators

This is one way (not the most efficient):

bool exactly_divisible_by_16( int number ) {

    // if a negative number is divisible by 16, then abs(number) is also divisible by 16
    if( number < 0 ) return exactly_divisible_by_16( -number ) ;

    // if we reach here, we know that number is non-negative
    if( number == 0 ) return true ; // zero is divisible by 16
    if( number < 16 ) return false ; // numbers in [1,15] are not divisible by 16

    // a number >= 16 is divisible by 16, if number-16 is divisible by 16
    // recursively reduce it to a number in [0,15] (by repeatedly subtracting 16 from it)
    return exactly_divisible_by_16( number-16 ) ; // true if number-16 is divisible by 16
}

[thmm]

Maybe like this:

bool is_divisible_by_16(int num)
{
    if (num < 0)
        num = -num;
        
    while (num > 0)
    {
        num -= 16;
        if (num == 0)
            return true;
        else if (num < 0)
            return false;
    }
    return true;
}

[lastchance]

bool isDiv16( int n ) { return !( n & 15 ); }