What is the difference b/w (long long int)1 << j and 1 << j in cpp

user_19902091 0
Viewed 40

first code:

void solve() {
  unsigned long long int l, r;
  cin >> l >> r;
  unsigned long long int ans = l ^ r;
  for (int i = 63; i >= 0; i--) {
    if ((ans >> i) & 1) {
      for (int j = i - 1; j >= 0; j--) {
        ans = (ans | (1 << j));
      }
      break;
    }
  }
  cout << ans << '\n';
}

Second code:

void solve() {
  unsigned long long int l, r;
  cin >> l >> r;
  unsigned long long int ans = l ^ r;
  for (int i = 63; i >= 0; i--) {
    if ((ans >> i) & 1) {
      for (int j = i - 1; j >= 0; j--) {
        ans = (ans | ((long long int)1 << j));
      }
      break;
    }
  }
  cout << ans << '\n';
}

The first code gives wrong answer for 1000000000 2000000000 and second gives right answer.

bit bit-manipulation c++
1 Answers
1 << j

will result in an int, so maximum of 32 bits accuracy. if j is above 31, the result is undefined, since the result is bigger than what a 32 bit integer can hold. reference:

When signed integer arithmetic operation overflows (the result does not fit in the result type), the behavior is undefined, — the possible manifestations of such an operation include:

  • it wraps around according to the rules of the representation (typically 2's complement),
  • it traps — on some platforms or due to compiler options (e.g. -ftrapv in GCC and Clang),
  • it saturates to minimal or maximal value (on many DSPs),
  • it is completely optimized out by the compiler.

Also if j is 31, the result will be negative because the signed bit will be overwritten.

(long long int)1 << j)

the result will be a 64 bit signed integer, and since j is never bigger than 62, the result is well defined.

user_60399950
Related