An example from an online test....

[Robert Hutchings]

Given an variable int N, write a function that will reverse all the bits
and return that changed integer variable.

[Drew Lawson]

In article <m16cvf$j0l$1...@dont-email.me>

Robert Hutchings <rm.hut...@gmail.com> writes:
>Given an variable int N, write a function that will reverse all the bits
>and return that changed integer variable.

I had that as a question in a face-to-face interview in 1992,
except that the data was a byte.


--
Drew Lawson

". . . And I never give a reason"
-- God, as channeled by Seven Nations

[Robert Hutchings]

On 10/9/2014 11:49 AM, Drew Lawson wrote:
> In article <m16cvf$j0l$1...@dont-email.me>
> Robert Hutchings <rm.hut...@gmail.com> writes:
>> Given an variable int N, write a function that will reverse all the bits
>> and return that changed integer variable.
>
> I had that as a question in a face-to-face interview in 1992,
> except that the data was a byte.
>
>

The online test was hosted by hackerrank.com. For a C++ Dev position, I
thought many of the questions were low-level C questions.

[mad...@acm.org]

On Thursday, October 9, 2014 12:26:47 PM UTC-4, Robert Hutchings wrote:
> Given an variable int N, write a function that will reverse all the bits
>
> and return that changed integer variable.

And you, of course, wrote:

int ReverseBits(int N)
{
return ~N;
}

Which really has nothing to do with C++ being a low-level C thing.

Randy.

[Robert Hutchings]

Exactly! Yes, it helps to have low-level "bits and bytes" knowledge,
but what about OO principles? Is multiple inheritance a good thing? How
is polymorphism handled by compilers? Those are questions I would have
expected...

[Robert Hutchings]

Another question was - what is the sizeof a struct with 1 int variable
and 2 virtual functions?

[Rick C. Hodgin]

On Thursday, October 9, 2014 1:39:44 PM UTC-4, mad...@acm.org wrote:
> On Thursday, October 9, 2014 12:26:47 PM UTC-4, Robert Hutchings wrote:
> > Given an variable int N, write a function that will reverse all the bits
> > and return that changed integer variable.
>

> int ReverseBits(int N)
> {
> return ~N;
> }
>
> Which really has nothing to do with C++ being a low-level C thing.
> Randy.

I would call that a flip bit function. A reverse bit function could
be interpreted as something like:

int ReverseBits(int N)
{
int i, N_new;

for (i = 0, N_new = 0; i < sizeof(int) * 8; i++, N >>= 1)
{
N_new <<= 1;
N_new |= (N & 0x1);
}

return N_new;
}

Best regards,
Rick C. Hodgin

[Robert Hutchings]

Yes, this is the algorithm that I found most often on the web. Again,
what relevance does this have to a C++ Dev?

[Rick C. Hodgin]

On Thursday, October 9, 2014 2:19:16 PM UTC-4, Robert Hutchings wrote:
> Yes, this is the algorithm that I found most often on the web. Again,
> what relevance does this have to a C++ Dev?

If I were guessing... it demonstrates a fundamental understanding of
how things operate below the C/C++ basic types. It lets them know
that you understand "the philosophy" of data, and not just the
workings of a language.

Perhaps they're thinking that without a solid foundation of the true
CPU fundamentals, anything you would pursue in C/C++ will be built atop
an unknown, rather than a concrete concept (bytes of data, and not C++
constructs like "int" and "char"), and that without this fundamental
tenant the rest will be unstable and shaky?

Perhaps that's their thinking. But, who knows? How does "Why are
manhole covers round?" relate to a developer's ability to write code?
Being creative in understanding an engineering concept doesn't always
translate into the kind of logical and procedural thinking required
to work through some complex algorithm.

Nonetheless, you may never know. In my experience, some interviewers
are just plain weird. :-) I once had an interviewer walk out of an
interview mid-stage because I didn't already know how something would
propagate through a macro during compilation. I told him I could compile
an example of the macro and see how it worked, and in that way understand
it, along with any other macros he'd like to show me. He felt that
already having that knowledge was more essential than being able to
figure out how to obtain knowledge I didn't already possess.

I'll never forget that interview. :-)

[Robert Hutchings]

Yes, I see what you mean. Well, whatever. I should hear back today on
my test results...

[Robert Wessel]

In this case it shows the incompetence of the test writer. Almost
certainly they *wanted* an answer along the lines of the above, but
that clearly does not work (portably) for negative inputs.

That being said, I have some sympathy for the HR department in
question. Having spent time on that side of the hiring desk, the raft
of BS you see from candidates makes one long for *any* tool to help
sort the wheat from the chaff.

[Martijn Lievaart]

On Thu, 09 Oct 2014 12:49:18 -0500, Robert Hutchings wrote:

> Another question was - what is the sizeof a struct with 1 int variable
> and 2 virtual functions?

That is completely implementation dependent, but one would expect sizeof
(int) + sizeof(vtable*) + padding.

M4

[Rick C. Hodgin]

On Thursday, October 9, 2014 2:53:14 PM UTC-4, robert...@yahoo.com wrote:
> In this case it shows the incompetence of the test writer. Almost
> certainly they *wanted* an answer along the lines of the above, but
> that clearly does not work (portably) for negative inputs.

That may have been part of the test. If so, switch the types to unsigned
int, cast the input to ReverseBits() as (unsigned int), and cast the
return as (int)N_new and now it works on all types. :-)

FWIW, I thought bitwise operations always worked properly on signed or
unsigned forms, in that they were implicitly cast to unsigned for the
scope of the bitwise operation.

[Robert Hutchings]

If you cast an int to an unsigned int, do you lose any of the bits? Are
any of the bits changed with this cast?

[Jorgen Grahn]

On Thu, 2014-10-09, Rick C. Hodgin wrote:
> On Thursday, October 9, 2014 2:19:16 PM UTC-4, Robert Hutchings wrote:
>> Yes, this is the algorithm that I found most often on the web. Again,
>> what relevance does this have to a C++ Dev?
>
> If I were guessing... it demonstrates a fundamental understanding of
> how things operate below the C/C++ basic types. It lets them know
> that you understand "the philosophy" of data, and not just the
> workings of a language.

> Perhaps they're thinking that without a solid foundation of the true

> CPU fundamentals [...]

Huh? The task was a plain old C++ one, which also happened to be more
or less the same in C.

The only weird "under the hood" part was doing it to an int rather
than an unsigned -- I don't know what it means to "reverse the bits"
of a signed integer, and I'm not sure I want to find out. It might
have been a bug in the test.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Rick C. Hodgin]

On Thursday, October 9, 2014 3:03:21 PM UTC-4, Robert Hutchings wrote:
> If you cast an int to an unsigned int, do you lose any of the bits? Are
> any of the bits changed with this cast?

You'll have to get a definitive answer from the C++ gurus around here. I
have discovered that my beliefs are often not exactly true with the C/C++
standards because I work with a specific compiler or two and they don't
always follow the standard.

I believe you wind up with the unsigned bit equivalent of whatever form
which existed in the signed value. It just now has no respect of sign
in operations. For positive signed int values, it's left exactly as it
is. For negative signed int values it will now be a very large value.

Still, it may be implementation specific, or there may be some quirk in
the C/C++ standards I don't know. In testing just now in MSVC++ 2008,
it had no difference. My original int algorithm also worked correctly
on both signed and unsigned inputs. But, as I understand the standard,
that behavior is implementation specific.

[Drew Lawson]

In article <o12jgb-...@news.rtij.nl>

I would think the key there is that the candidate knows it is
sizeof(vtable*) and not 2*sizeof(function*).


--
|Drew Lawson | If you're not part of the solution |
| | you're part of the precipitate. |

[Martijn Lievaart]

On Thu, 09 Oct 2014 19:16:31 +0000, Drew Lawson wrote:

> In article <o12jgb-...@news.rtij.nl>
> Martijn Lievaart <m...@rtij.nl.invlalid> writes:
>>On Thu, 09 Oct 2014 12:49:18 -0500, Robert Hutchings wrote:
>>
>>> Another question was - what is the sizeof a struct with 1 int variable
>>> and 2 virtual functions?
>>
>>That is completely implementation dependent, but one would expect sizeof
>>(int) + sizeof(vtable*) + padding.
>
> I would think the key there is that the candidate knows it is
> sizeof(vtable*) and not 2*sizeof(function*).

Which although true for any implementation I know, is implementation
dependent and rather irrelevant imho.

M4

[Jorgen Grahn]

On Thu, 2014-10-09, Rick C. Hodgin wrote:

> On Thursday, October 9, 2014 3:03:21 PM UTC-4, Robert Hutchings wrote:
>> If you cast an int to an unsigned int, do you lose any of the bits? Are
>> any of the bits changed with this cast?
>
> You'll have to get a definitive answer from the C++ gurus around here. I
> have discovered that my beliefs are often not exactly true with the C/C++
> standards because I work with a specific compiler or two and they don't
> always follow the standard.

They probably do, mostly, but the problem is that the standard is more
tolerant than any specific compiler. Google "all the world's a VAX".

> I believe you wind up with the unsigned bit equivalent of whatever form
> which existed in the signed value. It just now has no respect of sign
> in operations. For positive signed int values, it's left exactly as it
> is. For negative signed int values it will now be a very large value.

That explanation seems wrong to me, but I'm not very interested in
/what/ happens so I won't try to elaborate.

[Ben Bacarisse]

Robert Hutchings <rm.hut...@gmail.com> writes:

> On 10/9/2014 1:16 PM, Rick C. Hodgin wrote:

<snip>

>> int ReverseBits(int N)
>> {
>> int i, N_new;
>>
>> for (i = 0, N_new = 0; i < sizeof(int) * 8; i++, N >>= 1)
>> {
>> N_new <<= 1;
>> N_new |= (N & 0x1);
>> }
>>
>> return N_new;
>> }
>>

> Yes, this is the algorithm that I found most often on the web.

It's more efficient to do it in interleaved blocks, though it gets messy
if you need to make it portable to any int width. For 32 bits:

unsigned int reverse_bits(unsigned int n)
{
unsigned int m;
m = n >> 16 | n << 16;
n = (m << 8) & 0xff00ff00 | (m >> 8) & 0x00ff00ff;
m = (n << 4) & 0xf0f0f0f0 | (n >> 4) & 0x0f0f0f0f;
n = (m << 2) & 0xcccccccc | (m >> 2) & 0x33333333;
m = (n << 1) & 0xaaaaaaaa | (n >> 1) & 0x55555555;
return m;
}

<snip>
--
Ben.

[Paavo Helde]

dr...@furrfu.invalid (Drew Lawson) wrote in news:m16muf$1qdn$1
@raid.furrfu.com:

> In article <o12jgb-...@news.rtij.nl>
> Martijn Lievaart <m...@rtij.nl.invlalid> writes:
>>On Thu, 09 Oct 2014 12:49:18 -0500, Robert Hutchings wrote:
>>
>>> Another question was - what is the sizeof a struct with 1 int variable
>>> and 2 virtual functions?
>>
>>That is completely implementation dependent, but one would expect sizeof
>>(int) + sizeof(vtable*) + padding.
>
> I would think the key there is that the candidate knows it is
> sizeof(vtable*) and not 2*sizeof(function*).

I.e. that the candidate knows it is not more harmful to have N>1 virtual
functions in the class than one. If so, why not to ask that directly?

p

[Chris Vine]

Modulo arithmetic is performed for casts to unsigned, so bits are
changed by a cast from signed to unsigned for negative numbers if the
representation of negative signed values is not 2's complement:

§4.7/2 of C++11: "If the destination type is unsigned, the resulting
value is the least unsigned integer congruent to the source integer
(modulo 2 n where n is the number of bits used to represent the
unsigned type). [ Note: In a two’s complement representation, this
conversion is conceptual and there is no change in the bit pattern (if
there is no truncation). — end note ]"

Chris

[Robert Wessel]

On Thu, 9 Oct 2014 12:10:22 -0700 (PDT), "Rick C. Hodgin"
<rick.c...@gmail.com> wrote:

>On Thursday, October 9, 2014 3:03:21 PM UTC-4, Robert Hutchings wrote:
>> If you cast an int to an unsigned int, do you lose any of the bits? Are
>> any of the bits changed with this cast?
>
>You'll have to get a definitive answer from the C++ gurus around here. I
>have discovered that my beliefs are often not exactly true with the C/C++
>standards because I work with a specific compiler or two and they don't
>always follow the standard.
>
>I believe you wind up with the unsigned bit equivalent of whatever form
>which existed in the signed value. It just now has no respect of sign
>in operations. For positive signed int values, it's left exactly as it
>is. For negative signed int values it will now be a very large value.

That would certainly not be true on a one's-complement or signed
magnitude implementation. For example converting a -5 in a 16-bit int
from signed to unsigned will result in the value 65531 in any
implementation. That works fine on a two's complement implementation.
On a one's complement machine it would be converting from a bit
pattern of 0xfffa to 0xfffb, on a sign/mag machine, you'd convert from
0x8005 to 0xfffb. After bit reversing (in all cases), you'd have
0xdfff, or -8193, which you'll then convert back to signed. Again, OK
on the two's complement machine. On the ones complement machine you'd
end up with 0xdffe, and, I think, on a sign/mag machine, 0xa001. And
neither of those really match what I'd expect a bit reversal of the
original values would be.

And that's assuming you don't hit a trap representation for the one's
complement or sign/mag implementations.

[David Harmon]

On Thu, 09 Oct 2014 11:26:16 -0500 in comp.lang.c++, Robert
Hutchings <rm.hut...@gmail.com> wrote,

>Given an variable int N, write a function that will reverse all the bits
>and return that changed integer variable.

Since this is a c++ quiz, perhaps you should add
"by using std::reverse()".

[Robert Hutchings]

Looking at the variety of answers both here and on the web, I think this
question is more about creative thinking skills. There are many ways to
skin a cat, but which way is best?

[Mr Flibble]

Skinning a cat isn't a very Christian thing to say mate; re-educate
yourself to say "crack a nut" in future. Oh sorry, I forgot, the
Christian god is actually quite evil .. carry on.

/Flibble

[Mr Flibble]

Oops, sorry .. I confused you with Rick C. Hodgin. Safely ignore. :)

/Flibble

[Robert Hutchings]

You know something mate? Your contributions to this group are very uh,
shall we say, "poor". Sorry, but someone had to say it...and no, I have
no sausages...

[Robert Hutchings]

Whoops, my bad. Sorry, wrong person. Carry on!

[Richard Damon]

sizeof(int)*8 should more properly be sizeof(int)*CHAR_BITS (in case it
isn't 8)

Even better would be to build the loop using INT_MAX (or UINT_MAX) to
allow for padding bits (but then, if there are padding bits, can you
really "reverse" the bits?)

You then have to worry about if N was odd, or negative, the routine will
invoke undefined behavior, you really should move N to an unsigned int
and build in an unsigned int,

[Rick C. Hodgin]

Richard Damon wrote:
> [snip]

I agree. Also, I didn't know CHAR_BITS existed. :-)

[Robert Hutchings]

This was the first example I got from the internet:

* Function to reverse bits of num */
unsigned int reverseBits(unsigned int num)
{
unsigned int NO_OF_BITS = sizeof(num) * 8;
unsigned int reverse_num = 0, i, temp;

for (i = 0; i < NO_OF_BITS; i++)
{
temp = (num & (1 << i));
if(temp)
reverse_num |= (1 << ((NO_OF_BITS - 1) - i));
}

return reverse_num;
}

/* Driver function to test above function */
int main()
{
unsigned int x = 2;
printf("%u", reverseBits(x));
getchar();
}

[Ben Bacarisse]

Robert Hutchings <rm.hut...@gmail.com> writes:
<snip>

> This was the first example I got from the internet:
>

> /* Function to reverse bits of num */

> unsigned int reverseBits(unsigned int num)
> {
> unsigned int NO_OF_BITS = sizeof(num) * 8;
> unsigned int reverse_num = 0, i, temp;
>
> for (i = 0; i < NO_OF_BITS; i++)
> {
> temp = (num & (1 << i));
> if(temp)
> reverse_num |= (1 << ((NO_OF_BITS - 1) - i));
> }

If you are going to run a loop, it's better to use the type's limit as
Richard said. Personally, I'd run a loop with two bits moving in
opposite directions -- it makes things very clear:

for (unsigned bit = 1, mask = UINT_MAX/2 + 1; mask; mask >>= 1, bit <<= 1)
reverse_num |= n & mask ? bit : 0;

The code you found just looks way too fussy for my taste.

> return reverse_num;
> }
>
> /* Driver function to test above function */
> int main()
> {
> unsigned int x = 2;
> printf("%u", reverseBits(x));
> getchar();
> }

And that's a pretty bad driver. For what it's worth, the one I used to
test my version is

int main(int argc, char **argv)
{
if (argc == 2) {
unsigned int n = strtoul(argv[1], 0, 0);
std::cout << Bits(n) << "\n" << Bits(reverse_bits(n)) << "\n";
}
return 0;
}

(the Bits class has a << operator to output a sequence of zeros and ones).

--
Ben.

[Robert Hutchings]

Very nice and clean! Thanks for the input Ben.

[Richard Damon]

I suppose that sort of information gotten out of a test might be useful.

Of course the real feedback to get from giving this sort of question on
test is what questions does the applicant give back! I would much prefer
working with someone who asks the right questions back then blindly
plows ahead even though they have some questions.

[Scott Lurndal]

Robert Hutchings <rm.hut...@gmail.com> writes:
>Given an variable int N, write a function that will reverse all the bits
>and return that changed integer variable.

on ARMv8:

int
reverse(int n)
{
__asm__ __volatile__ ("rev %0, %1", "=r"(rval): "r"(n));
return rval;
}

Although technically, it should be an unsigned int.

[Scott Lurndal]

mad...@acm.org writes:
>On Thursday, October 9, 2014 12:26:47 PM UTC-4, Robert Hutchings wrote:

>> Given an variable int N, write a function that will reverse all the bits
>>
>> and return that changed integer variable.
>

>And you, of course, wrote:
>
>int ReverseBits(int N)
>{
> return ~N;
>}
>
>Which really has nothing to do with C++ being a low-level C thing.
>
>Randy.

That complements the bits, but doesn't reverse them (reversing is
when bit N-1 becomes bit 0,
bit N-2 becomes bit 1; where N is the size, in bits, of 'int').

[mad...@acm.org]

Yes, exactly so. I, however, took "reverse" to mean "invert", so I guess I would have failed the test. :-)

Randy.