Bitwise operator doesn't work as it supposed to in C++

Question

I'm trying to find whether a particular string has all unique characters in it or not. My approach is like this, I'm initializing a variable of 64 bit, say places and setting it to 0. Now, I'm iterating over the string and calculating the difference between of ASCII between current character and 'A'(smallest ASCII possible). If (places & (1"<<"pos)) is already set, the string does not have unique characters.

Everything works fine but with only lowercase characters. The moment I add test with uppercase, the code doesn't work anymore. I'm sure its something with my variable places but I don't know what exactly is wrong.

Here is the code for the same :

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

void check_unique(string s){
    int64_t places=0;       
    for(int i=0;i<s.length();i++){   
    int pos=s[i]-'A';            
    if((places & (1<<pos))!=0){  
        cout<<"String does not have all unique characters\n";   
        return;
    }
    places|=(1<<pos);            
  }
   cout<<"String has all unique characters\n";   
}

int main() {
    check_unique("abcde"); // Testcase 1
    check_unique("aabb");  // Testcase 2
    check_unique("ABbde");   // Testcase 3, Wrong output.
    return 0;
}

Less efficient but it looks really cool: `return std::unoreded_set{s.begin(), s.end()}.size() == s.size();` — NathanOliver, Sep 25 '18 at 18:17
Pop quiz: what do you get if you try `std::cout << (1 << 32) << std::endl;` The answer might surprise you. Now, compute the difference between the ascii value of lowercase and uppercase letters, and you should be able to figure it out yourself. — Sam Varshavchik, Sep 25 '18 at 18:18
@NathanOliver Thanks, but I am writing a tutorial and in that I am demonstrating different ways to do same task. I have written something very similar to what you mentioned already. Can you help me with this solution ? — Light Yagmi, Sep 25 '18 at 18:19
Hint: Hown many bits are allowed in a `int64_t` ? Compare with `pos - 'A'` — Ripi2, Sep 25 '18 at 18:20
@Quimby I did already. It is treating uppercase and lowercase same. I can't really figure out myself so came for help. — Light Yagmi, Sep 25 '18 at 18:20
Pop quiz #2: See what happens when you try to see what you get from `std::cout << (1 << n) << std::endl;` with `n` being an `int` value. Start with `n` being, oh, say 29, and work your way up, one bit a time. There's no reason for you to ask anything else, any more. This should be sufficient for you to figure it out, by yourself. Good luck. — Sam Varshavchik, Sep 25 '18 at 18:22
@Arkadiy: ASCII(A) = 65, ASCII(a)=97. And no UB because int64_t is signed — Ripi2, Sep 25 '18 at 18:22
Unrelated: `#include ` should not be used ([why](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h)) and `using namespace std;` should be avoided ([why](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)). Together they reinforce some of the other's worst behaviours, resulting in some very hard to understand errors. Do not do this. — user4581301, Sep 25 '18 at 18:27
@user4581301 My bad, I shouldn't use it definitely. Thanks for pointing out. — Light Yagmi, Sep 25 '18 at 18:38
@SamVarshavchik My '1' is 32 bit and left shifting it with >32 might returning a garbage value. Thanks for pointing out. — Light Yagmi, Sep 25 '18 at 18:38

score 4 · Accepted Answer · answered Sep 25 '18 at 18:23

4

In C++ constants have type, in your case 1 has type int and it seems your platform has 32 bit ints, so when you use lowercase letters you get out of range. Obvious solution is to use constant of type long - 1L or even better unsigned long 1UL. You can use cast as well:

static_cast<uint64_t>(1) << pos

answered Sep 25 '18 at 18:23

Slava

43,454
1
47
90

Some platforms only have 32 bit longs as well, so `1UL` won't work there either. use `UINT64_C(1)` to get a constant literal of type uint64_t.. – Chris Dodd Sep 25 '18 at 18:38
You were great help. I realised that my 1 is a 32 bit integer and I am left-shifting it with more than 32 bit, so it might be returning a garbage value. Thanks for pointing out. – Light Yagmi Sep 25 '18 at 18:40
1

@LightYagmi It doesn't evaluate a garbage value - it evaluates to 0. – 3Dave Sep 25 '18 at 18:41

Bitwise operator doesn't work as it supposed to in C++

1 Answers1