Friday, January 8, 2016

Digest for comp.lang.c++@googlegroups.com - 14 updates in 3 topics

Paul <pepstein5@gmail.com>: Jan 08 09:58AM -0800

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@slp53.sl.home (Scott Lurndal): Jan 08 06:14PM

>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);
 
>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.
 
 
>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 <grahn+nntp@snipabacken.se>: Jan 08 06:51PM

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 <pepstein5@gmail.com>: Jan 08 10:56AM -0800

On Friday, January 8, 2016 at 6:51:21 PM UTC, Jorgen Grahn wrote:
 
> 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 <grahn+nntp@snipabacken.se>: Jan 08 08:10PM

On Fri, 2016-01-08, Paul wrote:
>> 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
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
Paul <pepstein5@gmail.com>: Jan 08 12:18PM -0800

On Friday, January 8, 2016 at 8:10:56 PM UTC, Jorgen Grahn wrote:
 
> > 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 <myfirstname@osa.pri.ee>: Jan 08 11:10PM +0200

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).
 
 
> 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 <myfirstname@osa.pri.ee>: Jan 08 11:10PM +0200

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 <pepstein5@gmail.com>: Jan 08 02:05PM -0800

On Friday, January 8, 2016 at 6:14:24 PM UTC, Scott Lurndal wrote:
> >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.
 
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 <luca.risolia@linux-projects.org>: Jan 08 11:05PM +0100

Il 08/01/2016 19:14, Scott Lurndal ha scritto:
 
> 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();
"R. Schubert" <raphael.schubert@gmx.de>: Jan 08 06:07AM -0800

On Friday, December 25, 2015 at 12:34:37 AM UTC+1, Paavo Helde wrote:
 
> typedef char* charPtr;
> charPtr x = charPtr(z);
 
Why is it even allowed to convert pointers this way without an explicit
reinterpret_cast?
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Jan 08 05:03PM

On 08/01/2016 14:07, R. Schubert wrote:
>> charPtr x = charPtr(z);
 
> Why is it even allowed to convert pointers this way without an explicit
> reinterpret_cast?
 
It is: reinterpret_cast is a subset of the C-style cast sausages.
 
/Flibble
legalize+jeeves@mail.xmission.com (Richard): Jan 08 06:43PM

[Please do not mail me a copy of your followup]
 
"R. Schubert" <raphael.schubert@gmx.de> spake the secret code
>> charPtr x = charPtr(z);
 
>Why is it even allowed to convert pointers this way without an explicit
>reinterpret_cast?
 
Functional casts (i.e. T(value) to cast value to type T) are just
another way of writing C style casts. A C style cast can be any of:
 
- static_cast
- const_cast
- reinterpret_cast
 
I think the compiler is even free to do dynamic_cast.
 
This is why C style casts are bad form in a C++ code base. From
reading the code, you not only don't know what you're getting from the
compiler without thinking really hard about it, you have no idea what
the original programmer *intended* when they wrote the C style cast.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
The Terminals Wiki <http://terminals.classiccmp.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Jan 08 12:55AM +0100

On 1/8/2016 12:29 AM, Mr Flibble wrote:
> are we human or are we dancer sausages?
 
What is Dancer?
 
Dancer is a simple but powerful web application framework for Perl.
 
http://perldancer.org/
 
 
Cheers,
 
- Alf
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)