Bit Manipulation in Python and Java

Question

I am working on a problem wherein, the given array is as follows:

" Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. "

For example:

Input: [2,2,3,2]
Output: 3

I am trying to solve it using Bit Manipulation, and my code in Python is as follows:

def singleNumber(self, nums):

    ans = 0
    for i in range(31):
        summ = 0
        for num in nums:
            dig = (num>>i)&1
            if dig:
                summ += 1
        summ = summ%3
        if summ:
            ans = ans | summ<<i

    return ans

All I am trying to do is, get the last bit of each number in the array and count the number of ones that I get and then %3 to get the exact 1 bits that remain and shift it to make the correct answer.

This fails test cases which have negative inputs, something like:

[-2,-2,1,1,-3,1,-3,-3,-4,-2]
O/P: 2147483644
Expected O/P: -4

However, when I do the exact same thing in Java, it works! The code is as below:

class Solution {
public int singleNumber(int[] nums) {

    int ans = 0;
    int dig = 0;

    for(int i = 0; i <=31; i++){
        int sum = 0;
        for(int num: nums){

            dig = (num>>i)&1;
            if(dig!=0){
                sum = sum + 1;    
            }
            sum = sum%3;
        }
        if(sum!= 0){
            ans = ans | sum<<i;
        }

    }
    return(ans);
   }
}

How are the bits represented in Python that is causing this difference? Can someone please tell me the difference in bit manipulations in both the languages, Python and Java?

stackoverflow.com/questions/35578435/… might help

achAmháin
– achAmháin

2018-06-12 14:02:51 +00:00
Commented Jun 12, 2018 at 14:02 — achAmháin
– achAmháin, Commented Jun 12, 2018 at 14:02

REDDY PRASAD · Accepted Answer · 2018-06-12 14:28:22Z

1

java has 32-Bit fixed int size. But in python there is no explicitly defined limit for numbers. read at (Maximum value for long integer)

A hacky solution for your problem (may not work all cases) is

return ans - 2**(32-1)

answered Jun 12, 2018 at 14:28

REDDY PRASAD

1,4092 gold badges16 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Bit Manipulation in Python and Java

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related