1

I was trying to understand Bitmasking and came across this problem where i have to store number upto 64 (1<n<64) in O(1) complexity : Here I'm trying to make a Data Structure to store values as a set but in O(1) as I have constraints of 64

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;


class BitMask
{

public:
    ll n;
    BitMask()
    {
        //call the class as Bitmask varname;
        n = 0;
    }
    void insert(long long x) {
        n |= (1 << x);
    }
    void deleteItem(long long x) {
        if (n & (1 << x)) {
            n &= ~(1 << x);
        }
    }
    void print() {
        for (int i = 0; i < 64; i++) {
            if (n & (1 << i)) {
                cout << i << endl;
            }
        }
    }

};

//implementation
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    BitMask obj1;
    //insertion

    obj1.insert(1);
    obj1.insert(5);
    obj1.insert(3);
    obj1.insert(60);


    //print
    obj1.print();
    cout << endl;
    //deletion
    obj1.deleteItem(5);

    obj1.print();
    cout << endl;
    return 0;
}

Here The output was supposed to give

1, 3, 5, 60

1,3,60

But instead this is giving

1 3 5 28 33 35 37 60

1 3 28 33 35 60

Can some tell why these extra bits are called out?

Vivek Negi
  • 11
  • 2
  • 4
    Whichever C++ textbook taught you to use `` -- you need to throw it away and get a different C++ textbook. If you copied that off some web site, without any explanation, don't visit that web site any more. If you saw this in some clown's Youtube video, unsubscribe from that channel, you're not learning proper C++. This is not a standard C++ header file, many C++ compilers don't have it and will not compile the shown code. – Sam Varshavchik Oct 12 '22 at 13:52
  • You're iterating through the bits one-by-one. If you want to set individual bits, you'll have to set those bits, and nothing else. Setting individual bits goes like this: `n |= 0x01; n |= 0x02; n |= 0x04; n |= 0x08; n |= 0x10; n |= 0x20;` etc – SimonC Oct 12 '22 at 13:55
  • To set each bit, double the last value. 1, 2, 4, 8, 16, 32, 64, 128, etc – SimonC Oct 12 '22 at 13:55
  • @SimonC Thank you for your insightful comment . But here the issue I'm facing is how is 28th 33rd and 35th bits are set? – Vivek Negi Oct 12 '22 at 13:58
  • You need `1LL << x` and `1LL << i`, otherwise your bitshifting an int beyond its range and it won't have the expected result. – Artyer Oct 12 '22 at 14:00
  • 2
    `typedef long long ll; typedef vector vi;` -- Obvious signs of using "competitive coding" websites to learn C++. There is no need to obfuscate the code here -- spell out these types instead of hiding them behind macros/typedefs. You could have easily used something that conveyed the type, `int64_t` -- that is a mere 5 more keystrokes than `ll`, which looks like the number `11` when viewing your code. – PaulMcKenzie Oct 12 '22 at 14:00
  • @Artyer Thank you very much for the insightful comment . This is correct .Thank you – Vivek Negi Oct 12 '22 at 14:02
  • Note that (1 << 62LL) is typically 0 with compiler warning while (1LL << 62) is 4611686018427387904 without compiler warning. – Öö Tiib Oct 12 '22 at 14:03
  • The duplicate question is for C, not C++. You can't expect the people with C++ questions to look for answers in C, unless we are all willing to admit that they are related. This implies posting questions tagged [c] AND [c++] is sometimes ACCEPTABLE or even RECOMMENDED (like the duplicate question designated for this question). – franji1 Oct 12 '22 at 15:02

0 Answers0