Something about bits

[zacariaz]

I have a random inteeger that i need to check if meet a certain
criteria. The criteria is that when converted to binary it consist only
of 1's, no 0's.
If that criteria is met i allso need to know how many 1's it consist
of.

Values that would meet the first criteria is fx.
3
7
15
and the output i need will be:
3 = 2
7 = 3
15 = 4

it all seems fairly simple, but i cant seem to figure out how to do it
in a proper way. I could probably do some magic with log2, but that is
not the way i want to do it.

Any suggestions?

Thanks in advance.


Regards

 

[Steve Pope]

I have a random inteeger that i need to check if meet a certain
criteria. The criteria is that when converted to binary it consist only
of 1's, no 0's.
If that criteria is met i allso need to know how many 1's it consist
of.

Values that would meet the first criteria is fx.
3
7
15

3 = 2
7 = 3
15 = 4

it all seems fairly simple, but i cant seem to figure out how to do it
in a proper way. I could probably do some magic with log2, but that is
not the way i want to do it.

Add one, then check to see if it's a power of two (see FAQ 26.12).

This doesn't get you the second part of your answer. For that
you might want to use a loop.

Steve

 

[Alf P. Steinbach]

* (e-mail address removed):

I have a random inteeger that i need to check if meet a certain
criteria. The criteria is that when converted to binary it consist only
of 1's, no 0's.
If that criteria is met i allso need to know how many 1's it consist
of.

Values that would meet the first criteria is fx.
3
7
15
and the output i need will be:
3 = 2
7 = 3
15 = 4

it all seems fairly simple, but i cant seem to figure out how to do it
in a proper way. I could probably do some magic with log2, but that is
not the way i want to do it.

Any suggestions?

First, this is obviously homework, and it would be nice to mention that.

clc++-ers generally don't do other's homework, but we can help with
concrete C++ problems.

But you don't post any concrete C++ problem.

Now if you'd posted this in [comp.programming] it would have been
on-topic there (but also there with the caveat about homework), and
perhaps you'd receive answers such as "check that x+1 has exactly one
1-bit", which reduces the problem to counting 1-bits.

For counting 1-bits in almost any programming language, you can use
repeated division by 2 and checking the remainder each time. In C++ you
can also use the right-shift operator >>. And many other ways; it may
be a good idea to post again when you have some code to present.

 

[zacariaz]

Alf P. Steinbach skrev:

* (e-mail address removed):

First, this is obviously homework, and it would be nice to mention that.

clc++-ers generally don't do other's homework, but we can help with
concrete C++ problems.

You asume much thinking that this is homework.

But you don't post any concrete C++ problem.

Then let me show how i first thought of doing it.

#include <iostream>
#include <bitset>
unsigned int test(unsigned int i) {
std::bitset<32> B = i;
int n;
int j;
for (n = 0; n < 32 && B[n] == 1; n++) {}
for (j = n; j < 32 && B[j] == 0; j++) {}
if (j == 32)
return(n);
else
return(0);
}

int main() {
Prime prime;
for(int i = 3; ; i++) {
std::cout << i << " : " << prime.mersenne(i);
std::cin.get();
}
}

It work, but i think we can all agree that it is messy. The reason for
that? I dont have a clue how to do it endless i use log2, which i wont.
And why not use log2? just me being silly i think, but never the less
it can be done without it, i have allready princip, all i need it a
proper way to write the code.

Now if you'd posted this in [comp.programming] it would have been
on-topic there (but also there with the caveat about homework), and
perhaps you'd receive answers such as "check that x+1 has exactly one
1-bit", which reduces the problem to counting 1-bits.

For counting 1-bits in almost any programming language, you can use
repeated division by 2 and checking the remainder each time. In C++ you
can also use the right-shift operator >>. And many other ways; it may
be a good idea to post again when you have some code to present.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

 

[zacariaz]

the line "Prime prime" isnt suposed to be there.

 

[Salt_Peter]

I have a random inteeger that i need to check if meet a certain
criteria. The criteria is that when converted to binary it consist only
of 1's, no 0's.
If that criteria is met i allso need to know how many 1's it consist
of.

Values that would meet the first criteria is fx.
3
7
15
and the output i need will be:
3 = 2
7 = 3
15 = 4

std::bitset has a member function count() which returns the size_t
number of set bits in you binary.

 

[Jim Langston]

I have a random inteeger that i need to check if meet a certain
criteria. The criteria is that when converted to binary it consist only
of 1's, no 0's.
If that criteria is met i allso need to know how many 1's it consist
of.

Values that would meet the first criteria is fx.
3
7
15
and the output i need will be:
3 = 2
7 = 3
15 = 4

it all seems fairly simple, but i cant seem to figure out how to do it
in a proper way. I could probably do some magic with log2, but that is
not the way i want to do it.

Any suggestions?

Thanks in advance.


Regards

Sicne it's homework I won't give code, but will state how I would do it.

I would copy the value into another var so I can modify it.
I would do a for loop for the number of bits in the interger.
If my variable is 0, then all is finished. Grab the current iterator
count and exit for loop
If my variable & 1 is 1, then so far all bits set. shift right my
variable and continue loop
If my variable & 1 is not 1, then there is a 0 somewhere in the middle.
Check failed
end for loop

 

[campos]

Hi Steve,

I wonder where the FAQ is.
Thanks~

Add one, then check to see if it's a power of two (see FAQ 26.12).

This doesn't get you the second part of your answer. For that
you might want to use a loop.

Steve

 

[Steve Pope]

I wonder where the FAQ is.
Thanks~

www.parashift.com
Look for 26.12

Steve

 

[Old Wolf]

I have a random inteeger that i need to check if meet a certain
criteria.

"Criteria" is a plural -- if there is only one then it is a criterion.

The criteria is that when converted to binary it consist only
of 1's, no 0's.

Hint: what is the result of x & (x+1) if the number does meet that
criterion?

If that criteria is met i allso need to know how many 1's it consist
of.

Right-shift it by one until it is zero , and count how many
shifts were used.