Mixing
Trying to print every combination of bits , given a variable
Trying to print every combination of bits , given a variable
Lets say combinationlength=4.
My logic is create the array {0,0,0,0} add 1 to the last element until first element gets the value 1.Until then if with the addition of 1 the array[3] ends up in a 2 result then make it 0 and then traverse the array(reversed) given a counter variable and every first non 1 element make it 0 while making all elements before the value that first non 1 equal to 0.This is for 8 repetitions.How close am i?Can someone help me finish this?
combinationlength
array {0,0,0,0}
1
1
1
array[3]
2
0
counter variable
1
0
1
0
Also this doesnt run for some reason.Nothing gets printed and ends after 2 seconds.
I just noticed i am skipping a step but anyways.
I want in every iteration to have an array like the sequence.And not added printf("0"); and shortcuts like that.
void print(int combinationlength){
int i,j,count;
int a=combinationlength-1;
int c=combinationlength-1;
int b;
int array[4]={0};
while(array[0]!=1){
array[a]++;
if(array[a]==2){
array[a]=0;
for(b=a;b<=c-1;b--){
if(array[b]==0)
array[b]=1;
}
c--;
}
for(count=0;count<combinationlength;count++){
printf("%d",array[count]);
}
printf("n");
}
return 0;
}
UPDATED:(also updated my explanation above this ^^ block of code)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(){
int i,j,count;
int a=4-1;
int c=4-1;
int b;
int array[4]={0};
while(array[0]!=1){
array[a]++;
if(array[a]==2){
array[a]=0;
for(b=a-1;b>c-1;b--){
if(array[b]==0) array[b]=1;
else array[b]=0;
}
c--;
}
for(count=0;count<4;count++){
printf("%d",array[count]);
}
printf("n");
}
return 0;
}
The hardcoded number 4 is supposed to be the input variable.
Thats why im asking for help cause i dont know other way.Actually i dont even know my way.And also i want to use every bit of every combination to add it to a list so i should have access by someway..(array gives it so i went with it.)
– lowspacetop
Jun 29 at 7:09
If you want to use arrays, take a look at heap or bottom-up algorithms
– Cid
Jun 29 at 7:11
i'll brb in a few hours.
– lowspacetop
Jun 29 at 7:26
4 Answers
4
Your problem statement is confusing:
if with the addition of 1 the array[3] ends up in a 2 result then make it 0 and then traverse the array(reversed) given a counter variable and every first non 1 element make it 0 while making all elements before the value that first non 1 equal to 0.
1
array[3]
2
0
1
0
1
0
This basically means you want the first 0 element to remain 0 while making all elements before that first 0 set to 0.
0
0
0
0
As a consequence, the array contents would alternate between { 0, 0, 0, 0 } and { 0, 0, 0, 1 }, which is probably not the intent.
{ 0, 0, 0, 0 }
{ 0, 0, 0, 1 }
Let's assume your problem is to simulate a base-2 counter with 4 binary digits and you count from 0 to 8. Your code is a bit too complicated (pun intended ;-). You should simplify and use fewer index variables:
0
8
#include <stdio.h>
int main() {
int i;
int array[4] = { 0 };
while (array[0] != 1) {
for (i = 0; i < 4; i++) {
printf("%d ", array[i]);
}
printf("n");
for (i = 4; i-- > 0; ) {
array[i] += 1;
if (array[i] == 2) {
array[i] = 0;
} else {
break;
}
}
}
return 0;
}
Output:
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
Note how you can write a for loop that counts down from the length of the array, enumerating all valid index values while using the exact length of the array and using a test i-- > 0 that is correct for both signed and unsigned types. This trick is sometimes referred to as the downto operator, not a real operator but one can make it look like one as i --> 0.
for
i-- > 0
i --> 0
EDIT: to print the complete set of binary combinations, keep looping until i is -1:
i
-1
#include <stdio.h>
int main() {
int i;
int array[4] = { 0 };
for (;;) {
for (i = 0; i < 4; i++) {
printf("%d ", array[i]);
}
printf("n");
for (i = 4; i-- > 0; ) {
array[i] += 1;
if (array[i] == 2) {
array[i] = 0;
} else {
break;
}
}
if (i < 0) {
/* the array is too small, all combinations exhausted */
break;
}
}
return 0;
}
how can i print the other half of the combinations?what do i change?I copied it and it looks correct but it ends in 0000.Also thank you very much in this one .its exactly what i expected when i first started my thinking.
– lowspacetop
Jun 29 at 13:18
I mean to be logically correct.
– lowspacetop
Jun 29 at 13:25
What do you mean by print the other half of the combinations? Do you want to increase the array size to a full 8 bits?
– chqrlie
Jun 29 at 14:17
uhhh no i just want to print the 1001 1010 and onwards . The other 8 of the 2**4 combinations.
– lowspacetop
Jun 29 at 14:26
Then you do not want to stop when
array[0] == 1, but go on for 16 iterations.– chqrlie
Jun 29 at 14:27
array[0] == 1
So, I'm still not entirely sure I understand what you want. If I understood correctly, you want every combination of bits (i.e. zeros and ones) of a certain length. Doing the additions manually in an array feels very wasteful, so lets instead use what the CPU already has to offer - integer addition.
An example program, printing all the combinations of a certain length would look something like this:
#include <stdio.h>
void print(int len){
for (unsigned long sortOfAnArray = 0; sortOfAnArray < (1U << len); sortOfAnArray++) {
for (int i = len - 1; i >= 0; i--) {
printf("%lu", (sortOfAnArray >> i) & 1);
}
printf("n");
}
}
int main(void) {
print(5);
return 0;
}
To explain the steps, sortOfAnArray is our integer, stored in binary, we add 1 to it on every iteration so that we get the different combinations.
sortOfAnArray
In order to print it, we have to access elements individually, we do this with a combination of a bitshift and logical and (sortOfAnArray >> i) & 1. So, we shift the bits in the array by i to the right, and check if it has a 1 on the first position, in other words, we checked if sortOfAnArray[i]==1 (if this was an array).
(sortOfAnArray >> i) & 1
sortOfAnArray[i]==1
We use unsigned due to the standard and long in case you want up to 64 bits available (although long long would be even safer there).
long long
EDIT
To further explain how we extract a bit from the integer.
Assume we have the integer
`unsigned long long foo = 27`
if we look at the bit representation of that, we get 00...011011, where the total number of bits is 64, but there's just a lot of zeros, hence the dots. Now, say we want to know the value of the 1st bit from the right. We can find that out by using the logical and operation
`foo & 1`
This will apply the logical and to every pair of bits at the same position in the two integers (foo and 1), in this case this will give us 1:
foo -- 00...011011
1 -- 00...000001
foo & 1 -- 00...000001
If foo had 0 as the rightmost bit, the result would instead be 0, so this essentially allows us to read whether the first bit is set to 0 or 1.
How do we generalise this to the other bits?
We have two options, we can either move the bit in the 1 (1 << n shifts the 1 bit n moves to the left), if we use the logical and then, we will get 0 if foo has a 0 in the n-th position or some nonzero value (2^n) if it has a 1.
1 << n
The other option is to instead shift the bits of foo to the right, the upside of doing this is if foo had a 1 in the n-th position, the result will now be 1 rather than 2^n, whereas if it was 0 the result is still 0. Other than that the two approaches are equivalent.
This is how we come up with the final solution, that is, to access the n-th element (0-based counting) as follows:
(foo >> n) & 1
we move the bits of foo to the right by n and look if the first bit is set to 0 or 1. Essentially, the integer is storing 64 bits (we don't need to use all of them, of course) the same way we would do that in an array, but the approach is much more efficient. Among other things, we don't need to implement our own addition for the array, as you had attempted initially.
I dont even know if im correct here, but, I mentioned not doing printf("0") which is like a shortcut , and i think your code basicly does that. I want the value to be printed like a final result not by modifying certain parts.i want to use that number and not get a byproduct of it.Let me update my post and let me know if u can work on that.
– lowspacetop
Jun 29 at 11:02
That's exactly why it's printing a number that you can use... it's not printing
printf("0"), it's showing you how to access that particular number, which is either 0 or 1, you can do whatever you want with that number.– Qubit
Jun 29 at 11:09
printf("0")
0
1
How can i access, lets say the digits of 0001?In the same or in a seperate function.
– lowspacetop
Jun 29 at 11:13
Say you have 0001 stored in
a (i.e. unsigned int a = 1), to get the leftmost digit you do (a >> 0) & 1, 2nd from the left, replace 0 with 1, etc.– Qubit
Jun 29 at 11:14
a
unsigned int a = 1
(a >> 0) & 1
I'll come back to it but can you take a look at my attemp?I think i describe it well.
– lowspacetop
Jun 29 at 11:22
An integer already consists (most of the time) of 4 bytes = 32 bits. You can use a simple integer instead of an array.
However printing an integer in binary format is a bit tricky, I used the answer of this question to do it.
#include <stdio.h>
#define BYTE_TO_BINARY_PATTERN "%c%c%c%c%c%c%c%c"
#define BYTE_TO_BINARY(byte)
(byte & 0x80 ? '1' : '0'),
(byte & 0x40 ? '1' : '0'),
(byte & 0x20 ? '1' : '0'),
(byte & 0x10 ? '1' : '0'),
(byte & 0x08 ? '1' : '0'),
(byte & 0x04 ? '1' : '0'),
(byte & 0x02 ? '1' : '0'),
(byte & 0x01 ? '1' : '0')
int main(void) {
int a = 0;
int limit = 4;
while( (a & (1 << limit)) == 0)
{
printf("0b"BYTE_TO_BINARY_PATTERN"n", BYTE_TO_BINARY(a));
a++;
}
return 0;
}
Output:
0b00000000
0b00000001
0b00000010
0b00000011
0b00000100
0b00000101
0b00000110
0b00000111
0b00001000
0b00001001
0b00001010
0b00001011
0b00001100
0b00001101
0b00001110
0b00001111
Little explanation:
In the while loop I use a so called bit mask. (1 << limit) results in a binary 1 at the position limit, so in this case it would be 0b00010000. With the binary & I check if a has that bit, if yes the while loop ends.
(1 << limit)
limit
0b00010000
&
a
Whenever I have to do something involving iteration over combinations, I automatically think of Grey Codes / reverse binary coding. Below is my own implementation (it uses a different formula than the wiki, but still covers all the values). Note they won't be in order, but it does cover all combinations 0->2^n-1 and it is very fast since it only needs to change one value each time.
#include <stdio.h>
int main(int argc, char** argv) {
unsigned int length = 4;
unsigned int array[4] = {0, 0, 0, 0};
int i, j;
for (i = 0; i < 1 << length; i++) {
array[__builtin_ctz(i)] ^= 1;
printf("Array Values: ");
for (j = 0; j < length; j++) {
printf("%d ", array[j]);
}
printf("n");
}
return 0;
}
Output:
Array Values: 0 0 0 0
Array Values: 1 0 0 0
Array Values: 1 1 0 0
Array Values: 0 1 0 0
Array Values: 0 1 1 0
Array Values: 1 1 1 0
Array Values: 1 0 1 0
Array Values: 0 0 1 0
Array Values: 0 0 1 1
Array Values: 1 0 1 1
Array Values: 1 1 1 1
Array Values: 0 1 1 1
Array Values: 0 1 0 1
Array Values: 1 1 0 1
Array Values: 1 0 0 1
Array Values: 0 0 0 1
Note I use the __builtin_ctz() method to count trailing zeros quickly. I don't know if its implemented on any other compilers, but GCC supports it.
__builtin_ctz()
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
It might be faster if you simply used a single integer and some bitmasks.
– Qubit
Jun 29 at 7:08