Practical example of a static variable.

[Paul]

The code below the asterisks is from a book. Since I don't want to either plug the book or criticise the book, I'd like to leave the precise reference unstated. The code is supposed to count the number of bits set to 1 in a 32 bits unsigned int. The technique is to calculate the answer for a single byte, memoize the answer, and then apply the answer for all four bytes.

My questions are as follows:
1) The u at the end of 0xffu seems redundant. It just means the bit pattern 11111111. If there were 16 fs instead of 2fs, then it would be relevant, however. Am I correct that the u is redundant?

2) Does the word "static" in this context mean that bitInChar shouldn't change its value between function calls? What do we gain from the "static" concept here? If we omit "static" but leave bitInChar global, then we can demonstrate the use of the bit-count function by:

int main()
{
fillBitsInChar();
const int i = 3287665;
const int j = 679346;
std::cout << std::endl << countBitsConstantFor32BitsInt(i) << std::endl
<< countBitsConstantFor32BitsInt(j) << std::endl;
}

3) How about the following idea of mine below? We don't want to waste time with fillBitsInChar() multiple times. So maybe we can have a static bool to make sure it's only done once. Is this code immediately below ok?

unsigned int myCountBits( unsigned int n)
{

static bool uninitialised = true;
if(uninitialised)
fillBitsInChar();

uninitialised = false;

return countBitsConstantFor32BitsInt(n);
}

I think I've answered my own question because my idea doesn't work if bitChar is not static. Have I correctly understood why "static" is used by the author?

Many thanks for your help.

Paul


*****************************************************************
BEGINNING OF CODE FROM BOOK.

unsigned int countBits( unsigned int n)
{
unsigned int count = 0;
while (n)
{ count += n & 1;
n >>= 1;
}
return count;
}


static int bitInChar[256];
void fillBitsInChar()
{
for (unsigned int i = 0; i < 256; ++i)
bitInChar[i] = countBits(i);
}

unsigned int countBitsConstantFor32BitsInt( unsigned int n)
{
return bitInChar[ n & 0xffu] + bitInChar[( n >> 8) & 0xffu]
+ bitInChar[( n >> 16) & 0xffu] + bitInChar[( n >> 24) & 0xffu];
}

END OF CODE FROM BOOK.

[Scott Lurndal]

Paul <peps...@gmail.com> writes:
>The code below the asterisks is from a book. Since I don't want to either =
>plug the book or criticise the book, I'd like to leave the precise referenc=
>e unstated. The code is supposed to count the number of bits set to 1 in a=

With GCC:

long variable = 0xaaaa5555l;
size_t number_of_bits_in_long = __builtin_popcountl(variable);

> 32 bits unsigned int. The technique is to calculate the answer for a sing=

>le byte, memoize the answer, and then apply the answer for all four bytes.
>
>My questions are as follows:

>1) The u at the end of 0xffu seems redundant. It just means the bit pattern=
> 11111111. If there were 16 fs instead of 2fs, then it would be relevant, =

>however. Am I correct that the u is redundant?

If the 'u' isn't present, the compiler assumes it is a signed integer and
will sign-extend it to 32-bits. That would be bad, since the intent in the
code you've posted is to mask off all but the low-order 8 bits.


>
>2) Does the word "static" in this context mean that bitInChar shouldn't cha=
>nge its value between function calls? What do we gain from the "static" co=
>ncept here? If we omit "static" but leave bitInChar global, then we can de=

>monstrate the use of the bit-count function by:

static is a scope (visibility) identifier. In this case, file scope.

[Jorgen Grahn]

On Fri, 2016-01-08, Paul wrote:
> The code below the asterisks is from a book. Since I don't want to
> either plug the book or criticise the book, I'd like to leave the
> precise reference unstated.

Thanks, then I won't read the rest. I can understand if people want to
protect their friends, or the place they work, or their jobs ... but a
book which needs protecting from criticism is not worth my time.

/Jorgen

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

[Paul]

On Friday, January 8, 2016 at 6:51:21 PM UTC, Jorgen Grahn wrote:
> On Fri, 2016-01-08, Paul wrote:
> > The code below the asterisks is from a book. Since I don't want to
> > either plug the book or criticise the book, I'd like to leave the
> > precise reference unstated.
>
> Thanks, then I won't read the rest. I can understand if people want to
> protect their friends, or the place they work, or their jobs ... but a
> book which needs protecting from criticism is not worth my time.
>

Ok. I didn't want to get drawn into criticism of the book and then have to defend myself against its author or publisher.

If you feel strongly about references, the book is

A collection of Bit Programming Interview Questions Solved in C + + Antonio Gulli and the problem I'm asking about is number 8. Thanks,

Paul

[Jorgen Grahn]

On Fri, 2016-01-08, Paul wrote:
> On Friday, January 8, 2016 at 6:51:21 PM UTC, Jorgen Grahn wrote:
>> On Fri, 2016-01-08, Paul wrote:
>> > The code below the asterisks is from a book. Since I don't want to
>> > either plug the book or criticise the book, I'd like to leave the
>> > precise reference unstated.
>>
>> Thanks, then I won't read the rest. I can understand if people want to
>> protect their friends, or the place they work, or their jobs ... but a
>> book which needs protecting from criticism is not worth my time.
>
> Ok. I didn't want to get drawn into criticism of the book and then
> have to defend myself against its author or publisher.

I see what you mean, but it wouldn't occur to me to worry about that.
The way I see it, if you publish something, you're inviting
criticism. If you cannot deal with that, then you should simply not
publish -- you don't deserve being published.

And you're not even criticizing.

> If you feel strongly about references, the book is
>
> A collection of Bit Programming Interview Questions Solved in C + +
> Antonio Gulli and the problem I'm asking about is number 8. Thanks,

I do feel strongly about that, so thanks!

[Paul]

On Friday, January 8, 2016 at 8:10:56 PM UTC, Jorgen Grahn wrote:
> On Fri, 2016-01-08, Paul wrote:
> > On Friday, January 8, 2016 at 6:51:21 PM UTC, Jorgen Grahn wrote:
> >> On Fri, 2016-01-08, Paul wrote:
> >> > The code below the asterisks is from a book. Since I don't want to
> >> > either plug the book or criticise the book, I'd like to leave the
> >> > precise reference unstated.
> >>
> >> Thanks, then I won't read the rest. I can understand if people want to
> >> protect their friends, or the place they work, or their jobs ... but a
> >> book which needs protecting from criticism is not worth my time.
> >
> > Ok. I didn't want to get drawn into criticism of the book and then
> > have to defend myself against its author or publisher.
>
> I see what you mean, but it wouldn't occur to me to worry about that.
> The way I see it, if you publish something, you're inviting
> criticism. If you cannot deal with that, then you should simply not
> publish -- you don't deserve being published.
>
> And you're not even criticizing.
>
> > If you feel strongly about references, the book is
> >
> > A collection of Bit Programming Interview Questions Solved in C + +
> > Antonio Gulli and the problem I'm asking about is number 8. Thanks,
>
> I do feel strongly about that, so thanks!
>

Jorgen,

I understand your first post but I'm confused about your second post. I understood your first post as saying that you won't help me because I didn't give a reference.

I accepted that feedback and therefore gave the reference. However your second post continued to offer no help, and I'm puzzled as to why.

In abstract form, the dialogue seems to me to be like this.
Me: Please help me.
You: I won't help you because you didn't add X.
Me: Ok. I add X.
You: I still won't help you and I won't say why.

Paul

[Paavo Helde]

On 8.01.2016 19:58, Paul wrote:
> The code below the asterisks is from a book. Since I don't want to either plug the book or criticise the book, I'd like to leave the precise reference unstated. The code is supposed to count the number of bits set to 1 in a 32 bits unsigned int. The technique is to calculate the answer for a single byte, memoize the answer, and then apply the answer for all four bytes.
>
> My questions are as follows:
> 1) The u at the end of 0xffu seems redundant. It just means the bit pattern 11111111. If there were 16 fs instead of 2fs, then it would be relevant, however. Am I correct that the u is redundant?

Answered by Scott.

> 2) Does the word "static" in this context mean that bitInChar shouldn't change its value between function calls? What do we gain from the "static" concept here? If we omit "static" but leave bitInChar global, then we can demonstrate the use of the bit-count function by:

bitInChar is in global scope, so it has static duration regardless of
the 'static' keyword, this only affects visibility ('static' is a
heavily overloaded keyword).

>
> int main()
> {
> fillBitsInChar();
> const int i = 3287665;
> const int j = 679346;
> std::cout << std::endl << countBitsConstantFor32BitsInt(i) << std::endl
> << countBitsConstantFor32BitsInt(j) << std::endl;
> }
>
> 3) How about the following idea of mine below? We don't want to waste time with fillBitsInChar() multiple times. So maybe we can have a static bool to make sure it's only done once. Is this code immediately below ok?
>
> unsigned int myCountBits( unsigned int n)
> {
>
> static bool uninitialised = true;
> if(uninitialised)
> fillBitsInChar();
>
> uninitialised = false;
>
> return countBitsConstantFor32BitsInt(n);
> }

Generally this is not a good idea. First, it wastes time in each call;
second, it is not thread-safe (modifying shared state without proper
synchronization is always not thread-safe). I would suggest to
initialize the static lookup table in the start of the program, either
by an explicit call or by a constructor of some static C++ object. I
suspect also that in C++11 it could be initialized by some constexpr
function so that it is effectively calculated at compile time, not at
run time.

Anyway, this exercise is not very practical because in reality there are
other ways to count set bits in an int which probably works faster than
array lookup. See e.g.
"http://stackoverflow.com/questions/14555607/explanation-required-number-of-bits-set-in-a-number"

hth
Paavo

[Paavo Helde]

On 8.01.2016 22:18, Paul wrote:>>> On Friday, January 8, 2016 at 6:51:21

PM UTC, Jorgen Grahn wrote:
>>>> Thanks, then I won't read the rest.
>

> I understand your first post but I'm confused about your second post.
I understood your first post as saying that you won't help me because
I didn't give a reference.

He did not say that. He said that he would not read the rest of the
question. Without reading, how could he tell if he can or wants to
answer the question? Maybe he will answer later if he feels like so and
has spare time, maybe not.

Cheers
Paavo

[Paul]

Thanks for your help.

On my machine 0xff == 0xffu evaluates as true. If the u is necessary, could 0xff be unequal to 0xffu with different endianness?

Paul

[Luca Risolia]

Il 08/01/2016 19:14, Scott Lurndal ha scritto:
> Paul <peps...@gmail.com> writes:
>> The code below the asterisks is from a book. Since I don't want to either =
>> plug the book or criticise the book, I'd like to leave the precise referenc=
>> e unstated. The code is supposed to count the number of bits set to 1 in a=
>
> With GCC:
>
> long variable = 0xaaaa5555l;
> size_t number_of_bits_in_long = __builtin_popcountl(variable);

In portable C++ that would be:

std::bitset<32> variable{0xaaaa5555};
auto number_of_bits_1 = variable.count();

[Barry Schwarz]

On Fri, 8 Jan 2016 09:58:36 -0800 (PST), Paul <peps...@gmail.com>
wrote:

>The code below the asterisks is from a book. Since I don't want to either plug the book or criticise the book,
>I'd like to leave the precise reference unstated. The code is supposed to count the number of bits
>set to 1 in a 32 bits unsigned int. The technique is to calculate the answer for a single byte, memoize
>the answer, and then apply the answer for all four bytes.
>
>My questions are as follows:
>1) The u at the end of 0xffu seems redundant. It just means the bit pattern 11111111.
>If there were 16 fs instead of 2fs, then it would be relevant, however. Am I correct that the u is redundant?

I didn't try to determine if it makes a difference to the book's code
but the constant 0xff has type (signed) int and 0xffu has type
unsigned int. Since this constant is only used in conjunction with
the unsigned parameter n, having it unsigned eliminates the need to
perform any of the "usual arithmetic conversions" that occur when
signed and unsigned appear in the same expression.

>2) Does the word "static" in this context mean that bitInChar shouldn't change its value
>between function calls? What do we gain from the "static" concept here? If we

Since bitInChar is defined at file scope, its value is not dependent
on function calls. It only changes value when assigned to. What the
static qualifier does is give the name internal linkage which prevents
it from being accessed by name from a different translation unit.

>omit "static" but leave bitInChar global, then we can demonstrate the use of the bit-count function by:
>
>int main()
>{
> fillBitsInChar();
> const int i = 3287665;
> const int j = 679346;
> std::cout << std::endl << countBitsConstantFor32BitsInt(i) << std::endl
> << countBitsConstantFor32BitsInt(j) << std::endl;
>}
>
>3) How about the following idea of mine below? We don't want to waste time with fillBitsInChar() multiple
>times. So maybe we can have a static bool to make sure it's only done once. Is this code immediately below ok?

It is completely unnecessary. The expectation is your code would call
fillBitsInChar exactly once before you ever called
countBitsConstantFor32BitsInt, which you could then call as often as
you wanted. (Similar to calling srand exactly once before calling
rand as often as needed.)

>unsigned int myCountBits( unsigned int n)
>{
>
> static bool uninitialised = true;
> if(uninitialised)
> fillBitsInChar();
>
>uninitialised = false;
>
> return countBitsConstantFor32BitsInt(n);
>}
>
>I think I've answered my own question because my idea doesn't work if bitChar is
>not static. Have I correctly understood why "static" is used by the author?

Did you mean bitInChar? In what way does it not work? Without the
specifier static, bitInChar has external linkage and therefore static
duration. This means its lifetime is the entire execution of the
program and it retains its last_stored value throughout that lifetime.
The only effect the specifier has is to change the linkage from
external to internal.

>Many thanks for your help.
>
>Paul
>
>
>*****************************************************************
>BEGINNING OF CODE FROM BOOK.
>
>unsigned int countBits( unsigned int n)
>{
>unsigned int count = 0;
>while (n)
>{ count += n & 1;
>n >>= 1;
>}
>return count;
>}
>
>
>static int bitInChar[256];
>void fillBitsInChar()
> {
> for (unsigned int i = 0; i < 256; ++i)
> bitInChar[i] = countBits(i);
> }
>
> unsigned int countBitsConstantFor32BitsInt( unsigned int n)
> {
> return bitInChar[ n & 0xffu] + bitInChar[( n >> 8) & 0xffu]
> + bitInChar[( n >> 16) & 0xffu] + bitInChar[( n >> 24) & 0xffu];
> }
>
>END OF CODE FROM BOOK.

--
Remove del for email

[Jorgen Grahn]

On Fri, 2016-01-08, Paavo Helde wrote:
> On 8.01.2016 22:18, Paul wrote:>>> On Friday, January 8, 2016 at 6:51:21
> PM UTC, Jorgen Grahn wrote:
> >>>> Thanks, then I won't read the rest.
> >
> > I understand your first post but I'm confused about your second post.
> I understood your first post as saying that you won't help me because
> I didn't give a reference.
>
> He did not say that. He said that he would not read the rest of the
> question. Without reading, how could he tell if he can or wants to
> answer the question?

What really happened was I was tired and had a cold. I was happy to
see the reference, so thanking him for it (and going offtopic with
some loose feelings about how books should work, apparently) felt like
something I should do immediately.

> Maybe he will answer later if he feels like so and
> has spare time, maybe not.

After Paul named the book like I asked him to, I feel obliged to read
it. (I should probably have stated that explicitly to avoid this
subthread.)

But perhaps I have nothing interesting to say; we'll see.

[Jorgen Grahn]

On Fri, 2016-01-08, Paul wrote:

> On Friday, January 8, 2016 at 6:14:24 PM UTC, Scott Lurndal wrote:
>> Paul <peps...@gmail.com> writes:

...

>> >My questions are as follows:

The code was something like:

unsigned n = something;
some_array[ n & 0xffu ];

>> >1) The u at the end of 0xffu seems redundant. It just means the bit pattern=
>> > 11111111. If there were 16 fs instead of 2fs, then it would be relevant, =
>> >however. Am I correct that the u is redundant?
>>
>> If the 'u' isn't present, the compiler assumes it is a signed integer and
>> will sign-extend it to 32-bits. That would be bad, since the intent in the
>> code you've posted is to mask off all but the low-order 8 bits.

But bad in what sense? 0xff is an int, and it's never negative since
int IIRC is at least 16 bits.

It's unclear to me what happens in 'n & 0xff': if both are promoted to
int, or to unsigned. (I checked TC++PL, but failed to find anything
useful. I should really know these rules, but I think I instead tend
to stay away from the gray areas ...)

In practice I write those things like the book did, and I never got
even a warning from the compiler. On the other hand, when I use bit
operations like & or shifting, I always feel better if all the types
involved are unsigned, so I can't really complain about that 'u'.

...

> On my machine 0xff == 0xffu evaluates as true.

They do on every machine. It only gets interesting when you try
0xffffffff == 0xffffffffu on a machine with 32-bit ints, and I don't
know what happens then -- probably a warning from the compiler.

> If the u is necessary, could 0xff be unequal to 0xffu with different
> endianness?

Whatever happens, endianness never enters the picture. You can't see
endianness differences unless you use pointers and casts to break
through the type system down to the raw memory beneath.

[David Brown]

On 09/01/16 09:48, Jorgen Grahn wrote:
> On Fri, 2016-01-08, Paul wrote:
>> On Friday, January 8, 2016 at 6:14:24 PM UTC, Scott Lurndal wrote:
>>> Paul <peps...@gmail.com> writes:
> ...
>>>> My questions are as follows:
>
> The code was something like:
>
> unsigned n = something;
> some_array[ n & 0xffu ];
>
>>>> 1) The u at the end of 0xffu seems redundant. It just means the bit pattern=
>>>> 11111111. If there were 16 fs instead of 2fs, then it would be relevant, =
>>>> however. Am I correct that the u is redundant?
>>>
>>> If the 'u' isn't present, the compiler assumes it is a signed integer and
>>> will sign-extend it to 32-bits. That would be bad, since the intent in the
>>> code you've posted is to mask off all but the low-order 8 bits.
>
> But bad in what sense? 0xff is an int, and it's never negative since
> int IIRC is at least 16 bits.
>
> It's unclear to me what happens in 'n & 0xff': if both are promoted to
> int, or to unsigned. (I checked TC++PL, but failed to find anything
> useful. I should really know these rules, but I think I instead tend
> to stay away from the gray areas ...)
>

Since "n" is an unsigned int, both get promoted to unsigned.

But promotion of (signed) 0xff to unsigned does not change its value -
as you say, "int" must be at least 16 bit.

However, while the "u" in 0xffu is redundant as far as the meaning and
operation of the code is concerned, it is not bad practice to make it
clear to the reader that you are dealing entirely with unsigned integers
here.

[Paul]

Yes, this can also be directly tested by
std::cout << typeid(1u & 0xff).name();

The result is j which denotes unsigned.

Paul

[Paul]

Ok, thanks for the clarification. I've received a lot of help on this topic already from everyone on this thread, and have no further questions. The author of the book has a great concept -- a series of books on c++ interviews, each focusing on a particular topic -- for example, bit manipulation in c++, dynamic programming in c++ etc. etc. Even if the code and explanations are not great, I think it's a wonderful concept and am looking at the books in this series on that basis.

In other words, I'm sure there are other books which explain bit manipulation better. But I doubt there is a better book on the precise topic of bit manipulation in c++ interviews. The reason I doubt this is that I would expect that such a niche topic only has one book devoted entirely to it.

From experience, I felt that referencing the book would elicit a massive subthread attacking and defending the book and I wanted to avoid going off-topic.

Having said that, I welcome opinions on these books. I have the whole series, and would be interested in feedback. Although I already have them, opinions on whether they're good or bad may well influence how much time I spend on them.

The books are all by Antonio Gulli and are called:
A collection of bit programming interview questions solved in c++
A collection of design pattern interview questions solved in c++
A collection of dynamic programming interview questions solved in c++
A collection of graph programming interview questions solved in c++
A collection of tree programming interview questions solved in c++

Paul

[Öö Tiib]

On MSVC it is "unsigned int" already and with GCC it is easy to get
"unsigned int" as well, we just need to wrap their __cxa_demangle
to a function with sane C++ interface:

#include <iostream>
#include <memory>
#include <string>
#include <cxxabi.h>

std::string demangle(char const* name)
{
using c_char_ptr = std::unique_ptr<char, decltype(std::free)*>;

int status = -4;
c_char_ptr res {abi::__cxa_demangle(name, NULL, NULL, &status)
, std::free};
return (status==0) ? res.get() : name;
}

int main()
{
std::cout << demangle(typeid(1u & 0xff).name()) << '\n';
}

[Scott Lurndal]

It would be interesting to see if this devolves to a single
POPCOUNT instruction on architectures that have one (e.g. Intel,
ARM64, et. al).