using ``1ll<<(N-1)`` to assign a large number of value to a long long int variable

Question

The question I saw was stated: You are given an array A of size N. An element Ai is said to be charged if its value(Ai) is greater than or equal to Ki and Ki is the total number of subsets of the array A, that contains an element Ai.

The logic is simply the number of times a number comes as a subset is 2^N-1 times. But in some test cases, N was 4000+. so, 2^N-1 will be way beyond any variable type can hold but in editorial, the writer used 1ll<<(N-1). I know the left shift operator is X<<Y = X*2^Y. But what is this 1ll? And how is it able to store such large value?

#include <bits/stdc++.h>

#define M 1000000007

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    int N;
    cin >> N;
    long long arr[N];
    for (int i = 0; i < N; i++)
      cin >> arr[i];
    if (N >= 64)
      cout << 0 << endl;
    else {
      long long val = (1ll << (N - 1));
      long long ans = 0;
      for (int i = 0; i < N; i++)
        if (arr[i] >= val)
          ans = (ans + arr[i] % M) % M;
      cout << ans << endl;
    }
  }
}

1<<N-1 explains 2^N-1 but does the 1ll means that it can take upto long long and long long val = 1ll<<N-1; means it can go upto 128bit?

Two things: First of all C++ doesn't really have [variable-length arrays](https://en.wikipedia.org/wiki/Variable-length_array), though some compilers add it as a non-portable extensions. Secondly please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — Some programmer dude, Jun 11 '19 at 09:47
`long long` is a 64-bit type on current platforms, so `1ll << N-1` can't go above 64 bits — phuclv, Jun 11 '19 at 10:21

KamilCuk · Accepted Answer · 2019-06-11T16:43:03.370

But what is this 1ll?

The 1ll is an integer literal. 1 is an an decimal literal and ll is an integer suffix. The suffix ll means that the type of the integer literal is long long int. The 1 means that the value of the literal is, well, 1.

And how is it able to store such large value?

I think you are asking about the line:

long long val = (1ll << (N - 1));

Because of the if (N >= 64) .. else before, we know that N < 64. So the maximum number could be:

1ll << 63 - 1   =
1ll << 62       =
0x4000000000000000

Which is just a number that fits in long long int type. The long long int type has at least 64 bits.

Without the ll suffix, the 1 would have the type int. On architectures where int type is narrower then 64 bits, ex. 16 bits, then undefined behavior would happen. Left shifting a variable by a number greater or equal to the length in bits of the left operant is undefined behavior, see ex. this question.

If you are asking about the line :

ans = (ans + arr[i] % M) % M;

It is calculating the sum modulo #define M 1000000007. It is common to do assignments/homework that calculate sum modulo this number, see ex this or this. The algorithm calculates the sum modulo 1000000007, not the whole number, that's why it is able to store it inside long long variable.

using ``1ll<<(N-1)`` to assign a large number of value to a long long int variable

1 Answers1