I've been learning C for a few weeks and I'm trying to make a program where the user input numbers between 0 and 5000, and when -1 is the input, the program shall print all the previous values in ascending order using bit operators. This is my code:
#include <stdio.h>
#include <stdlib.h>
int main(){
unsigned int x[200];
int w, y, z;
while (1){
printf("Insert a value between 0 and 5000: \n");
scanf("%d", &x[w]);
if (x[w] == -1) {
break;
}
y = y | (1 << x[w]);
w ;
}
printf("\n");
for (int z = 0; z < 5001; z ) {
if (y & (1 << z)) {
printf("%d\n", z);
}
}
return 0;
}
But everytime after the first value is inserted the program ends. How can I fix it? Thanks for any help.
CodePudding user response：
Sounds like you are effectively creating a lookup table, mapping the numbers 0..5000 to a bit indicating whether that number was input or not.
For that, you will need 5001 bits. On a system with 32-bit unsigned int values, that's will require ceil( 5001 / 32 ) = 157 of them. So 200 is more than enough.
But your logic for setting and looking up bits is entirely incorrect.
What you want to do can be achieved by using integer division to determine the correct array element to modify. The remainder of that division identifies which bit to access.
#define UINT_BITS ( sizeof( unsigned ) * CHAR_BIT )
void set_bit( unsigned *a, unsigned i ) {
a[ i / UINT_BITS ] |= 1u << ( i % UINT_BITS );
}
int get_bit( unsigned *a, unsigned i ) {
return ( a[ i / UINT_BITS ] >> ( i % UINT_BITS ) ) & 1;
}
Note that your program removes duplicates outputs. If a number is input twice, it will only be output once.
CodePudding user response：
Based on your question tags, I assume you're asking about creating a bitset to store all of the values.
In this case, I recommend creating a special struct, and using functions to access and set the values within the bitset. This will help you understand and maintain your code. Consider this example:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#define BITSET_LEN 5000
#define BITSET_BYTES ((BITSET_LEN 7) / 8)
typedef struct {
uint8_t bytes[BITSET_BYTES];
} bitset_t;
bitset_t bitset_new () {
bitset_t b = {0};
return b;
}
bool bitset_get (const bitset_t * self, size_t index) {
if (index > BITSET_LEN) {
// TODO handle error here
}
size_t byte_index = index >> 3;
size_t bit_index = index & 0b111;
uint8_t byte = self->bytes[byte_index];
return (byte >> bit_index) & 1;
}
void bitset_modify (bitset_t * self, size_t index, bool value) {
if (index > BITSET_LEN) {
// TODO handle error here
}
size_t byte_index = index >> 3;
size_t bit_index = index & 0b111;
uint8_t mask = 1 << bit_index;
if (value) {
self->bytes[byte_index] |= mask;
} else {
self->bytes[byte_index] &= ~mask;
}
}
int main() {
bitset_t bits = bitset_new();
while (1) {
int input=0;
printf("Insert a value between 0 and %d\n", BITSET_LEN);
scanf("%d", &input);
if (input >= BITSET_LEN) {
printf("%d is too large.\n", input);
} else if (input < 0) {
break;
} else {
// Set the bit
bitset_modify(&bits, input, true);
}
}
printf("\n");
for (size_t i=0; i<BITSET_LEN; i) {
if (bitset_get(&bits, i)) {
printf("%ld\n", i);
}
}
}
There are a few things that I changed from your example to make my example.
First, I created a struct just for storing bits. This will let you pass around pointers to bitsets in a more regular way, and improve the clarity of the code. Combined with the creation of separate functions to get and set bits, it's easier to understand which sections of the code do what.
I also chose to use uint8_t from stdint.h instead of unsigned int. uint8_t is an unsigned, 8 bit integer. Using an explicity sized type improves the portability of the code. Additionally, if we used larger types we would have to worry about endianess.
In both the bitset_get and bitset_modify methods, we have to calculate the byte_index and bit_index. In your example, you tried to shift bits directly by the entire size. You cannot do this. You can only do bitshifts smaller than the size of the field you are shifting. You have to calculate how many bytes over to access, and then what bit index within that byte you wish to access for larger fields.
This is surprisingly easy, because there are 8 bits in a byte, and 8 is a power of 2. This means that for any binary number, we can split it in two.
Index format:
01010101
XXXXX-----> index of byte
XXX -> 0 to 7, index of bit
The smaller 3 bits form the index of the bit. We can take just the smallest 3 bits by taking the number & 0b111. The rest is the byte index, which we access by shifting the bits over by 3.
CodePudding user response：
As others have noted, the OP code demonstrates a misconception. Bits are not magically shifted left from one byte (or int) to the next like a game of Telephone. The code, written by a coder, has to do the heavy-lifting to achieve what the task requires.
Okay, so you need lots of bits. Any single set bit can only mark if a value has been entered at least once. Repetitions of the same value would require more elaborate recordkeeping.
Simply define an array of unsigned bytes (each 8 bits wide), initialised to 0's, and sufficiently large to store the range expected (0-5000). You want to ensure that the number of bits is at least sufficient, so allocating an extra byte is insurance and insignificant.
Because the suggested range is positive values to 5000, this code "bails out" when the user enters any negative value.
#include <stdio.h>
int main() {
unsigned char bits[ (5000 8) / 8 ] = { 0 }; // about 625 bytes for 0-5000
int x = 1;
while( x >= 0 ) { // terminate on -ve input
printf( "Value 0-5000 (neg=done): " );
if( scanf( "%d", &x ) != 1 ) {
fprintf( stderr, "scanf burped. entry rejected." );
continue;
}
// Use integer division and modulo to set the appropriate bit
if( 0 <= x && x <= 5000 ) // verify value in range before using it
bits[ x/8 ] |= (1 << (x%8));
else
printf( "%d is out of range. Rejected.\n", x );
}
printf( "\n" );
// now, "sweep" up across all the stored bits (0 or 1), printing when a set bit encountered
int z = 0;
for( int i = 0; i < sizeof bits/sizeof bits[0]; i )
for( uint8_t m = 1; m; m <<= 1, z )
if( bits[i] & m )
printf( "%d\n", z );
return 0;
}