Dynamic programming bits

[vrakas]

Hello.
I am coding a dynamic solution to a problem with buttons.
a button can be on or off. there are n buttons
so i thought of trying all possibilities of bits(1 or 0) of length n
for example for n=3
000
001
010
011
100
110
111
do you have any idea how i can iterate through all these for any n?
Thanks

[Script Coder]

what is the problem description?

[vrakas]

its not just about this problem. i actually get this idea on many problems. but i never knew how to do it so i did something else. this is just an example.

[Script Coder]

well in that case, i think that could be a solution.

[vrakas]

which? ;p i am asking for help on how to implement this

[tmihos]

In case than you need an integer that represent what buttons are down and what are up, you can compute the number:
int i = a[0]*1 + a[1]*2 + a[2]*4 + a[3]*8 +...
This number is unique for every image of up-down buttons

[vrakas]

the problem is to get the array a ;p i did what you said but it's impractical so i asked here to see if there is anything easier(with bitsets for example)

[tmihos]

If we understand the same problem, a[j] have values 0-->>down or 1-->>up

[gtm]

think of it as having a n-bit binary number,

interate through each number from 0 to (2^n)-1, and at each iteration use the bit shift operator << and then AND that bit with 1 to print out whether or not a 1 or 0 is in that location.

in this manner you can have someone input a value for n and it will give you all the possible iterations. Though you can clearly see youll have 2^n iterations no matter what n you give

[gtm]

here, was fun

#include <iostream>
#include <math.h>

void printBinary(const unsigned char val, int n) {
  for(int i = n-1; i >= 0; i--)
    if(val & (1 << i))
      std::cout << "1";
    else
      std::cout << "0";
}

int main() {
  while(true){
    unsigned int getN;
    unsigned char a;
    std::cout<<"Please enter N number of buttons"<<std::endl;
    std::cin>>getN;
    int n = (int)pow(2, getN); 
  
    for(int i = 0; i < n; i++){
      a = i;
      std::cout<<i<<": ";
      printBinary(a, getN);
      std::cout<<std::endl;
    }     
  }
}

though note: this only works up to n 8.. due to the fact that char only holds 8 bits.. but, im sure you can figure out a way to work beyond this ;)

[zb0S216C]

gtm wrote:

"due to the fact that char only holds 8 bits.."

No. A byte can have any amount of bits so long as the byte can represent the value 255.

_Wazzak

[gtm]

What.

1 byte = 8 bits

[zb0S216C]

That's an assumption, not a fact. Not every system has an 8-bit byte.

_Wazzak

[tmihos]

bits: 10110011 = 8 bits = 179

[gtm]

Now I realize I am a newb here and to C++ and all but I have to respectfully disagree with you.

A byte is always 8 bits.

What changes system per system is how many bits represent certain types such as a char, integer, or float for instance.

[tmihos]

Is 8 bits that can represent numbers form 0 to 255 with all posible compinations. Like 0-999 in normal numbers basis 10 represents 1,000 numbers with 3 decimal "bits"

[cire]

http://stackoverflow.com/questions/5516044/system-where-1-byte-8-bit

[zb0S216C]

gtm wrote:

"I realize I am a newb here and to C++"

That's why you're not understanding me. The C++ Standard formally states that the amount of bits "char" must represent is 8 at minimum (2⁸). Therefore, any number of bits per byte is to be assumed. While 8 is usually the normal amount of bits that form a byte, this cannot be assumed as in some cases, this is purely implementation specific.

_Wazzak

[gtm]

All that means is that a "char" is a minimum of 8 bits. This does not mean that any number of bits to a byte can be assumed.. it still holds true that 8 bits is a byte.. youre getting confused.. a char is not explicitly a byte, nor vice versa. So on one system say a char is made up of 12 bits. This does NOT mean that there are 12 bits to a byte.

[cire]

All that means is that a "char" is a minimum of 8 bits.

standard wrote:

1.7 The C++ memory model [intro.memory]
The fundamental storage unit in the C++ memory model is the byte. A byte is at least large enough to contain any member of the basic execution character set (2.3) and the eight-bit code units of the Unicode UTF-8 encoding form and is composed of a contiguous sequence of bits, the number of which is implementation defined.

Clearly, a byte is not restricted to an octet.