C / C ++ bit-bit or bit-vector

Question

I am learning C / C ++ programming and have come across using “bit arrays” or “bit vectors”. Not able to understand their purpose? here are my doubts -

• Are they used as boolean flags?
• Can arrays be used intinstead? (more memory, of course, but ..)
• What is the concept of bit masking?
• If bit-masking is a simple bit-wise operation to get the appropriate flag, how to make one program for them? Is it easy to perform this operation in the head to see what the flag will be, as indicated in decimal numbers?

I am looking for applications to better understand. for Eg -

Q. You are given a file containing integers in the range (from 1 to 1 million). There are several duplicates, and therefore some numbers are missing. Find the fastest way to find missing numbers?

In the question above, I read solutions suggesting using bit arrays. How can I store each integer several times?

Answer 1

I think you are confused between arrays and numbers, in particular, what it means to manipulate binary numbers.

. , , . 1,2,3,4... , , , , ?

1, 2, 4, 8, 16... , . ? , 2, 00000000, 2, . 1, 4 8. , 00001101. , = 1 * 2 ^ 0, 1 * 2 ^ 2 1 * 2 ^ 3. 13.

, , . , , 8, 8 = 00001000. , , , :

  00001101
& 00001000
= 00001000

, , - , 1, 1, 0.

, C:

int func(...)
{
    int retval = 0;

    if ( sometestthatmeans an error )
    {
        retval += 1;
    }


    if ( sometestthatmeans an error )
    {
        retval += 2;
    }
    return retval
}

int anotherfunc(...)
{
    uint8_t x = func(...)

    /* binary and with 8 and shift 3 plaes to the right
     * so that the resultant expression is either 1 or 0 */
    if ( ( ( x & 0x08 ) >> 3 ) == 1 )
    {
        /* that error occurred */
    }
}

, . , xml .., , . (, 2) , , .

, . , ( ). , ... .

Answer 2

:

, "1 ", 1 . , - ( ).

- - .

, 0 4, : 0 0 0 0 0. : 3, 2, 2 : read 3 → 0 0 0 1 0. read 3 (again) → 0 0 0 1 0. read 2 → 0 0 1 1 0. : 0,1,4 -

BTW, , , ( ) 32

Answer 3

- - . , , Bool, Bool , .

, ( , , , ), .

, C ( , int i:1;, " " ), , ( ).

" ". int 32 , , sizeof (int), . ( ) , >> 5 / 32 & 31 % 32, , .

#include <stdio.h>
#include <errno.h>
#include <stdint.h>

int main(){
    /* put all numbers from 1 to 1000000 in a file, except 765 and 777777 */
    {
        printf("writing test file\n");
        int x = 0;
        FILE * f = fopen("testfile.txt", "w");
        for (x=0; x < 1000000; ++x){
            if (x == 765 || x == 777760 || x == 777791){
                continue;
            }
            fprintf(f, "%d\n", x);
        }
        fprintf(f, "%d\n", 57768); /* this one is a duplicate */
        fclose(f);
    }

    uint32_t bitarray[1000000 / 32];

    /* read file containing integers in the range [1,1000000] */
    /* any non number is considered as separator */
    /* the goal is to find missing numbers */
    printf("Reading test file\n");
    {
        unsigned int x = 0;
        FILE * f = fopen("testfile.txt", "r");
        while (1 == fscanf(f, " %u",&x)){
            bitarray[x / 32] |= 1 << (x % 32);
        }
        fclose(f);
    }
    /* find missing number in bitarray */
    {
        int x = 0;
        for (x=0; x < (1000000 / 32) ; ++x){
            int n = bitarray[x];
            if (n != (uint32_t)-1){
                printf("Missing number(s) between %d and %d [%x]\n",
                    x * 32, (x+1) * 32, bitarray[x]);
                int b;
                for (b = 0 ; b < 32 ; ++b){
                    if (0 == (n & (1 << b))){
                        printf("missing number is %d\n", x*32+b);
                    }
                }
            }
        }
    }
}

Answer 4

- - . , , , -/ . , , .

- , , 8,16,32 64 . , 16 , 4 , 2 , - 10 . 3 8,8 16 , 50% .

-, pinvoke/interop .. p >

Answer 5

This is used to store bit flags, as well as to parse different fields of binary protocols, where 1 byte is divided into several bit fields. This is widely used in protocols such as TCP / IP, up to ASN.1 encodings, OpenPGP packets, etc.