Xxoorr problem

1

any idea what’s wrong with this code.I am debugging this from 3 days and not able to find any problem.compiler is also not giving any warnings

#include"bits/stdc++.h"
using namespace std;
bool getBit(long long int x,long long int pos)
{
        return (( x & (1 << pos)) != 0);

}
int main(void) {
	// your code goes here
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	long long int t;
	cin>>t;
	while(t--)
	{
	    long long int n,k;
	    cin>>n>>k;
	    
	    vector<long long int> bits(32,0);
	    
	    vector<long long int> arr(n);
	    long long int count=0;
	   
	    for(long long int i=0;i<n;i++)
	    {
	        cin>>arr[i];
	        if(arr[i]!=0)
	        {
	        for(int j=31;j>=0;j++)
	        {
	            
				//storing how many set bits are present at a particular position j
	             if(getBit(arr[i],j))
	              bits[j]++;
	        }
	          count++;
	        }
	        
	    }
	    if(count==0)
	    {
	        cout<<0<<"\n";
	        continue;
	    }
	    
	    long long int ans=0;
	    
	    for(int i=0;i<32;i++)
	    {

	       if(bits[i]<=k&&bits[i]!=0)
	         ans++;
	       
		   
		   else{
	           ans=ans+(bits[i]/k);
	           ans++;
	       }  
	    }
	    cout<<ans<<endl;
	    
	    
	    
	}
	return 0;
}
1 Like
2

Segmentation fault?

Issue found using GDB 
suman@skynet:~/temp$ c++ -g -o wrong wrong.cpp 
suman@skynet:~/temp$ gdb wrong
GNU gdb (Ubuntu 9.2-0ubuntu1~20.04) 9.2
Copyright (C) 2020 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from wrong...
(gdb) run < in.in > out2.out
Starting program: /home/suman/temp/wrong < in.in > out2.out

Program received signal SIGSEGV, Segmentation fault.
main () at wrong.cpp:34
34		              bits[j]++;
(gdb)

Apparently, it should have been
for(int j = 31; j >= 0; j--)

instead of
for(int j = 31; j >= 0; j++)

1 Like
3

I haven’t read the full code (so there may be more bugs), but getBit function is incorrect. Never compare the result of a bitwise operation to an int. Try calling this function for any input… it wud always return true

4

No, it’s not.

He is using this function to check if j^{th} bit (from the right end) is set or not. And it’s working perfectly fine. The following code shows it.

Testing the function getBit 
#include <bits/stdc++.h>
using namespace std;

bool getBit(long long int x,long long int pos)
{
    return (( x & (1 << pos)) != 0);
}

int main()
{
    int N = 13;
    cout << (getBit(N, 0) ? "YES" : "NO") << '\n';
    cout << (getBit(N, 1) ? "YES" : "NO") << '\n';
    cout << (getBit(N, 2) ? "YES" : "NO") << '\n';
    cout << (getBit(N, 3) ? "YES" : "NO") << '\n';

    return 0;
}

Output:

YES
NO
YES
YES
1 Like
5

why is it that some compiler show more precise warnings than others

6

By the way I tried again after making this correction and it is giving 33 as output which is wrong answer(for sample test cases)
any idea why?

7

If a code compiles without any warnings, that doesn’t mean that code is bug free.

9

Your logic is incorrect (probably).
I am pasting my code here.

C Code 
#include <stdio.h>

int main() {
    int t = 0;
    scanf("%d", &t);
    for(; t > 0; t--) {
        int n = 0, k = 0;
        scanf("%d%d", &n, &k);
        int count[30] = {0};
        for(int i = 0; i < n; i++) {
            int a = 0;
            scanf("%d", &a);
            for(int bit = 0; bit < 30 && a > 0; bit++) {
                count[bit] += (a&1);
                a >>= 1;
            }
        }
        int ans = 0;
        for(int i = 0; i < 30; i++) {
            ans += count[i] / k + (count[i] % k ? 1 : 0);
        }
        printf("%d\n", ans);
    }
    return 0;
}
11

But I have used same logic as yours.only the method of storing bits is little different

12

Consider the following input.
Input

5
10 9
9 10 4 2 2 1 2 2 6 7
5 10
5 10 9 2 3
9 3
0 2 0 10 6 9 5 0 4
6 4
3 10 1 1 5 5
2 6
5 2

Expected Output

4
4
4
5
3

Your Output

32
32
32
33
32
13

yeah that’s what i am saying.
it is giving 32 for every input
i am not able to figure out why.
i did a dry run on this code and was not able to find any problem

14

No, that’s not the only difference.

Replace:

        for(int i=0;i<32;i++)
        {

           if(bits[i]<=k&&bits[i]!=0)
             ans++;


           else{
               ans=ans+(bits[i]/k);
               ans++;
           }
        }

with

for(int i = 0; i < 30; i++) {
            ans += count[i] / k + (count[i] % k ? 1 : 0);
        }

(adapted from @suman_18733097) and you’ll get the correct answer for the sample testcase, at least.

The two blocks of code are entirely different. For example, with yours, ans will always be at least 32.

1 Like
15

That’s strange, which compiler are you using, in mine it always gives true… so instead I simply use (x & (1 << pos) if I want true and !(x & (1 << pos) if I want false

16

Anyways, for him, other bugs like incorrect ceil function and j++ instead of j-- wud be causing the issue

17

Am I missing something?
Ain’t both the same?

18

ok now i got the mistake i was making
thanks

1 Like
19

I mean if (x & (1 << pos)) {...} simply and not equating to 0 or 1 as it will anyways return true if pos-th bit is set… no need to code if (x & (1 << pos) == 1) {...}
You are right and equating won’t make a difference, I just prefer the former because on my local machine somehow the latter doesn’t work

20

This won’t work, as if the pos bit is set, the result of x & (1 << pos) will be 1 << pos, not 1.

2 Likes
22

yes exactly, that’s why never equate bitwise expressions to any number