BitMap solution to save some space(JAVA)


  • 0

    Each bit mark one number. Initial set all bit to be '1'.

    Modify '1' to '0' if the number has been browsed.

    public class Solution {
        public int countPrimes(int n) {
            if(n <= 2){
                return 0;
            }
            
            byte[] bitMap;
            if(n % 8 == 0){
                bitMap = new byte[n / 8];
            }
            else{
                bitMap = new byte[n / 8 + 1];
            }
            //set all bits to be '1'
            for(int i = 0; i < bitMap.length; i++){
                bitMap[i] = -1;
            }
            
            int result = 0;
            //start from 2 to n
            for(int i = 2; i < n; i++){
                int index = (i - 1) / 8;
                int indexBit = (i - 1) % 8;
                if(oneToZero(bitMap,index,indexBit)){
                    result ++;
                    int next = i + i;
                    while(next < n){
                        index = (next - 1) / 8;
                        indexBit = (next - 1) % 8;
                        oneToZero(bitMap,index,indexBit);
                        next += i;
                    }
                }
            }
            return result;
        }
        
        public boolean oneToZero(byte[] bitMap, int index, int indexBit){
            switch(indexBit){
                case 0:
                    if((bitMap[index] & 0x80) != 0){
                        bitMap[index] &= 0x7f;
                        return true;
                    }
                    else{
                        return false;
                    }
                case 1:
                    if((bitMap[index] & 0x40) != 0){
                        bitMap[index] &= 0xbf;
                        return true;
                    }
                    else{
                        return false;
                    }
                case 2:
                    if((bitMap[index] & 0x20) != 0){
                        bitMap[index] &= 0xdf;
                        return true;
                    }
                    else{
                        return false;
                    }
                case 3:
                    if((bitMap[index] & 0x10) != 0){
                        bitMap[index] &= 0xef;
                        return true;
                    }
                    else{
                        return false;
                    }
                case 4:
                    if((bitMap[index] & 0x08) != 0){
                        bitMap[index] &= 0xf7;
                        return true;
                    }
                    else{
                        return false;
                    }
                case 5:
                    if((bitMap[index] & 0x04) != 0){
                        bitMap[index] &= 0xfb;
                        return true;
                    }
                    else{
                        return false;
                    }
                    case 6:
                    if((bitMap[index] & 0x02) != 0){
                        bitMap[index] &= 0xfd;
                        return true;
                    }
                    else{
                        return false;
                    }
                case 7:
                    if((bitMap[index] & 0x01) != 0){
                        bitMap[index] &= 0xfe;
                        return true;
                    }
                    else{
                        return false;
                    }
            }
            return false;
        }
        
        
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.