프로그래밍기초 제14주 실습과제

       

비트 연산자(bitwise operators)

       


아래 모든 문제에 적용되는 지시 사항

  • BitOperation.java이라는 이름의 자바 파일을 만든 후 BitOperation 클래스 안에 아래의 함수들을 작성하세요.
  • 주석의 첫 부분은 /** 로 시작하고 끝 부분은 */로 마칩니다.
  • 주석을 적어 넣지 않거나 들여쓰기를 하지 않으면 감점합니다.
  • 총 7개의 문제가 있으며 모두 10점 만점으로 채점합니다. 즉, 14주차 과제의 만점은 70점입니다.
  • P8은 30점짜리 보너스 문제입니다. 다른 문제에서 감점이 있을 경우 최대 30점을 이 문제에서 만회할 수 있습니다.
  • 14주차 문제는 모두 ‘비트 연산자’를 활용하여 문제를 해결해야 합니다. 반드시 비트 단위 연산을 사용하여 문제를 해결해야 정답으로 인정합니다.

       

P1 (비트 갯수 세기)

주어진 정수의 비트 표현에서 1의 개수를 세어 반환하는 메서드를 작성하세요.

bitCount라는 이름의 메서드를 작성합니다. 이 메서드는 정수형 변수 하나를 매개변수로 받아 이 변수의 비트 표현을 보고 1의 개수를 세어 반환합니다.

public static int bitCount(int input){
    // 함수 내용을 작성하세요.
}

아래와 같은 코드를 실행하면,

System.out.println("P1---");
System.out.println(bitCount(15));
System.out.println(bitCount(-15));

아래와 같은 출력이 나와야 합니다.

P1---
4
29

 

[힌트]

왼쪽 끝의 한 비트만 1인 mask를 만든다.

int mask = 1 << 31;

주어진 정수 input과 mask를 & 연산하면 그 결과는, input의 왼쪽 끝 비트가 0인 경우 0이고, 1인 경우 0이 아니다. 연산 결과가 0이 아니면 count를 증가시킨다.

mask를 오른쪽으로 한 칸 unsigned시프트시킨다. (왼쪽 끝에 0이 들어간다.)

mask = mask >>> 1

주어진 정수 input과 mask를 & 연산하면 그 결과는, input의 왼쪽 끝 두 번째 비트가 0인 경우 0이고, 1인 경우 0이 아니다. 연산 결과가 0이 아니면 count를 증가시킨다.

위 과정을 반복한다. mask의 비트들이 모두 0이 될 때까지.

마지막으로 count를 반환한다.

   

P2 (정수를 비트 문자열로 변환하기)

주어진 정수의 비트 표현형을 문자열 변수에 담아 반환하는 메서드를 작성하세요.

toBinaryString이라는 이름의 메서드를 작성합니다. 이 메서드는 정수형 변수 하나를 매개변수로 받아 이 변수의 비트 표현을 문자열로 변환하여 반환합니다. 이 때, 반드시 비트 연산자를 사용해야 합니다.

메서드를 작성한 후 자바의 표준 API인 Integer.toBinaryString() 메서드와 출력값을 비교하세요. 어떤 정수가 입력으로 들어가더라도 Integer.toBinaryString()와 우리가 작성한 toBinaryString 메서드가 동일한 문자열을 출력해야 합니다.

  • 자바의 int 자료형은 4바이트의 메모리를 사용하여 숫자를 표현하므로 출력 문자열의 길이는 최대 32입니다. 숫자의 맨 앞에 0이 연속해서 나오는 경우는 생략해서 출력합니다.
  • 문자열 간의 비교를 위해서는 compareTo() 메서드를 사용해야 합니다. 이 메서드는 두 문자열이 같을 경우 0을 출력합니다. (13주차 수업 참고)

프로그램 예시

public class BitOperation {
    public static void main(String[] args) {
        System.out.println(toBinaryString(0));
        System.out.println(toBinaryString(5));
        System.out.println(toBinaryString(-5));

        System.out.println(toBinaryString(24).compareTo(Integer.toBinaryString(24)));
    }

    public static String toBinaryString(int input){
        // 함수 내용을 작성하세요.
    }
}

출력 예시

0
101
11111111111111111111111111111011
0

 

[힌트]

주어진 정수의 메모리를 검사하여 그에 따라 0과 1로 구성되는 문자열을 조합해야 합니다. String은 한 번 만들어지면 그 내용을 바꿀 수 없으므로 (immutable) “0” 혹은 “1” 문자열을 32번 더하기하면 그 때마다 새로운 String 인스턴스를 만들게 되어 낭비가 큽니다. 그래서 String을 더하는 대신 편집 가능한 (내용을 변경할 수 있는) StringBuilder를 사용합니다. 9주차 강의자료 (ppt) 56쪽~59쪽을 참고하세요.

우선 0과 1로 만들어진 문자열을 저장할 StringBuilder 인스턴스를 하나 만듭니다.

주어진 정수를 오른쪽으로 한 칸씩 시프트하면서 1과 & 연산을 수행합니다. 그 결과가 0이 아닐 때는 문자열 ”1”을, 0일때는 문자열 “0”을 StringBuilder에 append합니다. 주어진 정수 정수를 시프트해 나가다가 그 값이 0이 되면 (1이 모두 밀려 나가고 나면) 시프트를 중단하고 StringBuilder의 문자열을 순서를 바꾸고 문자열로 변환하여 반환합니다. StringBuilder의 문자열 순서를 바꾸려면 StringBuilder.reverse() 메소드를 사용합니다.

StringBuilder sb = new StringBuilder("순서");
sb.reverse();
System.out.println(sb.toString());  // "서순"

위와 같이 하면 주어진 정수가 0인 경우에는 빈 문자열을 반환하게 됩니다. 그러니까 주어진 정수가 0일 때는 특별히 “0”을 반환하도록 별도로 처리해 주어야 합니다.

       

P3 (홀수 여부 판별하기)

주어진 정수가 홀수인지 판별하는 메서드를 작성하세요.

isOdd라는 이름의 메서드를 작성합니다. 이 메서드는 정수형 변수 하나를 매개변수로 받아 이 변수가 홀수인지 아닌지 판단하여 참 또는 거짓을 불 자료형으로 반환합니다.

public static boolean isOdd(int input){
    // 함수 내용을 작성하세요.
}
  • 자바에서는 아래와 같이 나머지 연산자를 활용하여 주어진 정수가 홀수인지 짝수인지를 판단할 수 있으나 본 과제에서는 나머지 연산자를 사용하지 말고 비트 연산자를 사용하여 홀 수 여부를 판단하세요.
input % 2 == 0

 

아래 코드를 실행하면,

System.out.println("P3---");
System.out.println(idOdd(1232));
System.out.println(isOdd(-1232));
System.out.println(isOdd(13));
System.out.println(isOdd(-13));

아래와 같은 출력이 나와야 합니다.

P3---
false
false
true
true

       

P4 (2의 지수승 여부 확인하기)

주어진 정수가 2의 지수승인지 여부를 판단하는 메서드를 작성하세요. isPower라는 이름의 메서드를 작성합니다. 이 메서드는 정수형 변수 하나를 매개변수로 받아 이 변수가 2의 지수승인지를 판단하고 참 또는 거짓을 불 자료형으로 반환합니다.

public static boolean isPower(int input){
    // 함수 내용을 작성하세요.
}
  • 메서드의 입력값으로는 1보다 큰 양의 정수가 들어온다고 가정합니다.
  • 함수 안에서 반복문을 사용하지 말고 비트 연산자를 사용하여 지수승 여부를 판별하도록 코드를 작성하세요.
  • 2의 보수 체계에서 2의 지수승 숫자가 갖는 특징을 활용하세요. 예를 들어, $2^4$의 경우 아래와 같은 형태의 이진수로 표현됩니다.
    00000000000000000000000000010000
    

    이 때, $2^4 - 1$의 경우 아래와 같이 표현됩니다.

    00000000000000000000000000001111
    

    위의 두 표현을 보면 모든 자릿수에서 1이 동시에 존재하는 경우가 없음을 알 수 있습니다. 이러한 현상은 모든 양의 정수들 중에서 2의 지수승인 수에 대해서만 적용됩니다. 이렇듯, 임의의 2의 지수승 $2^k$와 $2^k-1$ 사이의 관계를 이용하여 위 함수를 작성하세요.

 

아래와 같은 코드를 실행하면,

System.out.println("P4---");
System.out.println(isPower(256));
System.out.println(isPower(1));
System.out.println(isPower(15));

아래와 같은 출력이 나와야 합니다.

P4---
true
true
false

       

P5 (2의 지수승으로 곱하기) 임의의 정수 $x$와 $k$가 주어졌을 때, $x \times 2^k$를 출력하는 메서드를 작성하세요. multiplyByPower라는 이름의 메서드를 작성합니다. 이 때, $x \times 2^k$의 값은 자바의 int 자료형이 갖는 값의 범위를 넘지 않는다고 가정합니다.

public static int multiplyByPower(int x, int k){
    // 함수 내용을 작성하세요.
}

 

아래와 같은 코드를 실행하면,

System.out.println("P5---");
System.out.println(multiplyByPower(3, 1));
System.out.println(multiplyByPower(-3, 1));
System.out.println(multiplyByPower(3, 0));
System.out.println(multiplyByPower(-3, 0));
System.out.println(multiplyByPower(3, 10));
System.out.println(multiplyByPower(-3, 10));

아래와 같은 출력이 나와야 합니다.

P5---
6
-6
3
-3
3072
-3072

 

[힌트]

간단한 정수를 메모리에 나타낸 후 $2^1$, $2^2$, $2^3$을 곱하면 어떻게 되는지 살펴보시오.

       

P6 (2의 지수승으로 나눈 후 몫과 나머지 구하기) 임의의 정수 $x$와 $k$가 주어졌을 때, $x$를 $2^k$로 나눈 후 몫과 나머지를 출력하는 메서드를 작성하세요. divideByPower라는 이름의 메서드를 작성합니다.

public static void divideByPower(int x, int k){
    int quotient; // 몫
    int remainder; // 나머지

    // 함수 내용을 작성하세요.

    System.out.println("몫: " + quotient + ", 나머지: " +  remainder);
}

 

아래와 같은 코드를 실행하면

System.out.println("P6---");
divideByPower(5, 1);
divideByPower(5, 2);
divideByPower(341, 5);
divideByPower(0, 0);
divideByPower(0, 1);

아래와 같은 출력이 나와야 합니다.

P6---
몫: 2, 나머지: 1
몫: 1, 나머지: 1
몫: 10, 나머지: 21
몫: 0, 나머지: 0
몫: 0, 나머지: 0

       

P7 (2의 거듭제곱수으로 나눈 후 몫과 나머지 구하기)

P6과 같은 계산을 하지만 화면에 몫과 나머지를 출력하는 대신, 몫과 나머지를 int 배열에 넣고 그 배열을 반환하는 메소드를 작성하세요. divideByPower2라는 이름의 메서드를 작성합니다. 반드시 시프트 연산을 이용하세요

public static int[] divideByPower2(int x, int k){
  // 함수 내용을 작성하세요.
}

  아래 코드를 실행하면,

System.out.println("P7---");
int[] r;
r = divideByPower2(5, 1);
System.out.println("몫: "+ r[0] + ", 나머지: " + r[1]);
r = divideByPower2(5, 2);
System.out.println("몫: "+ r[0] + ", 나머지: " + r[1]);
r = divideByPower2(341, 5);
System.out.println("몫: "+ r[0] + ", 나머지: " + r[1]);
r = divideByPower2(0, 0);
System.out.println("몫: "+ r[0] + ", 나머지: " + r[1]);
r = divideByPower2(0, 1);
System.out.println("몫: "+ r[0] + ", 나머지: " + r[1]);

P6과 같은 출력이 나와야 합니다.

       

P8 (부분집합 출력하기)

정수의 집합이 정수 배열의 형태로 주어졌을 때, 이 집합으로부터 홀수로 이루어진 부분 집합을 모두 출력하는 메서드를 작성하세요. printOddSubset라는 이름의 메서드를 작성합니다.

 

프로그램 예시

public class BitOperation {
    public static void main(String[] args) {
        int[] array = {4, 1, 2, -3, 5};

        printOddSubset(array);
    }

    public static void printOddSubset(int[] array) {
        for (int i = 1; i < (1 << array.length); i++) { // 전체 부분 집합에 대해 반복
            int[] temp = new int[array.length]; // 임시 부분 집합 만들기          
            int count = 0; // 새로운 배열 크기 기억하기
            boolean isOdd = true; // 홀수 여부 확인

            // 함수 내용을 작성하세요.

            if (isOdd) {
                // Arrays.toString과 Arrays.copyOf는 자바의 표준 API 메서드로 배열 temp 에서 count 개의 원소만을 출력하도록 한 것입니다.
                System.out.println(Arrays.toString(Arrays.copyOf(temp,count)));
            }
        }
    }
}

출력 예시

[1]
[-3]
[1, -3]
[5]
[1, 5]
[-3, 5]
[1, -3, 5]