함수 설계 f (f (n)) == -n [닫힘]
지난 인터뷰에서 내가받은 질문 :
다음
f과 같은 기능을 설계하십시오 .f(f(n)) == -n
n32 비트 부호있는 정수 는 어디에 있습니까 ? 복소수 산술을 사용할 수 없습니다.전체 숫자 범위에 대해 이러한 함수를 설계 할 수없는 경우 가능한 가장 큰 범위로 설계하십시오.
어떤 아이디어?
어때 :
f (n) = 부호 (n)-(-1) n * n
Python에서 :
def f(n):
if n == 0: return 0
if n >= 0:
if n % 2 == 1:
return n + 1
else:
return -1 * (n - 1)
else:
if n % 2 == 1:
return n - 1
else:
return -1 * (n + 1)
파이썬은 정수를 임의 길이 long으로 자동 승격합니다. 다른 언어에서는 가장 큰 양의 정수가 오버플로되므로 해당 정수를 제외한 모든 정수에 대해 작동합니다.
그것은 실수 작동하려면 당신은 교체해야 N 에서 (-1) N 과 함께 { ceiling(n) if n>0; floor(n) if n<0 }.
C #에서 (오버플로 상황을 제외하고 모든 double에 대해 작동) :
static double F(double n)
{
if (n == 0) return 0;
if (n < 0)
return ((long)Math.Ceiling(n) % 2 == 0) ? (n + 1) : (-1 * (n - 1));
else
return ((long)Math.Floor(n) % 2 == 0) ? (n - 1) : (-1 * (n + 1));
}
당신은 그들이 어떤 종류의 언어를 기대했는지 말하지 않았습니다. 여기에 정적 해결책이 있습니다 (Haskell). 기본적으로 가장 중요한 두 비트를 엉망으로 만듭니다.
f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30
| otherwise = complementBit x 30
동적 언어 (Python)에서는 훨씬 쉽습니다. 인수가 숫자 X인지 확인하고 -X를 반환하는 람다를 반환합니다.
def f(x):
if isinstance(x,int):
return (lambda: -x)
else:
return x()
추가 정보 (int의 32 비트 제외)를 사용하지 않는 경우 모든 숫자에 대해 이러한 함수가 존재할 수없는 이유에 대한 증거가 있습니다.
f (0) = 0이어야합니다. (증명 : f (0) = x라고 가정합니다. 그러면 f (x) = f (f (0)) = -0 = 0. 자, -x = f (f (x )) = f (0) = x, 즉 x = 0입니다.)
또한, 어떤을 위해 x하고 y, 가정 f(x) = y. f(y) = -x그때 우리는 원합니다 . 그리고 f(f(y)) = -y => f(-x) = -y. 요약하면 : 만약 f(x) = y, 다음 f(-x) = -y,와 f(y) = -x,와 f(-y) = x.
따라서 0을 제외한 모든 정수를 4의 집합으로 나눌 필요가 있지만 이러한 정수는 홀수입니다. 뿐만 아니라 양수 대응이없는 정수를 제거해도 2 (mod4) 숫자가 있습니다.
(abs 값으로) 남은 최대 수 2 개를 제거하면 함수를 얻을 수 있습니다.
int sign(int n)
{
if(n>0)
return 1;
else
return -1;
}
int f(int n)
{
if(n==0) return 0;
switch(abs(n)%2)
{
case 1:
return sign(n)*(abs(n)+1);
case 0:
return -sign(n)*(abs(n)-1);
}
}
물론 또 다른 옵션은 0을 준수하지 않고 제거 된 2 개의 숫자를 보너스로받는 것입니다. (그러나 그것은 단지 어리석은 경우입니다.)
C ++의 오버로딩 덕분에 :
double f(int var)
{
return double(var);
}
int f(double var)
{
return -int(var);
}
int main(){
int n(42);
std::cout<<f(f(n));
}
또는 전처리기를 남용 할 수 있습니다.
#define f(n) (f##n)
#define ff(n) -n
int main()
{
int n = -42;
cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}
이것은 모든 음수에 해당됩니다.
f (n) = abs (n)
2의 보수 정수에 대한 양수보다 음수가 하나 더 많기 때문에는와 동일한 솔루션 f(n) = abs(n)보다 하나 더 많은 경우에 유효합니다 . 당신을 하나 ... : Df(n) = n > 0 ? -n : nf(n) = -abs(n)
최신 정보
아니요, litb의 의견으로 방금 인식 한 것처럼 한 가지 경우 더 유효하지 않습니다 abs(Int.Min).
나도 모드 2 정보를 사용하는 것에 대해 생각했지만, 결론을 내 렸습니다. 올바르게 수행 Int.Min하면 오버플로를 제외하고 모든 숫자에 대해 작동합니다 .
최신 정보
나는 좋은 비트 조작 트릭을 찾고 잠시 동안 그것을 가지고 놀았지만, mod 2 솔루션이 하나에 맞는 동안 좋은 한 줄의 라이너를 찾을 수 없었습니다.
f (n) = 2n (abs (n) % 2)-n + sgn (n)
C #에서는 다음과 같이됩니다.
public static Int32 f(Int32 n)
{
return 2 * n * (Math.Abs(n) % 2) - n + Math.Sign(n);
}
이 모든 값에 대한 작업을하려면, 당신은 교체해야 Math.Abs()와 (n > 0) ? +n : -n와의 계산에 포함 unchecked블록. 그런 다음 Int.Min확인되지 않은 부정이 수행하는 것처럼 자체적으로 매핑됩니다.
최신 정보
다른 답변에서 영감을 받아 함수가 작동하는 방식과 그러한 함수를 구성하는 방법을 설명하겠습니다.
처음부터 시작하겠습니다. 함수 f는 주어진 값에 반복적으로 적용되어 n일련의 값을 생성합니다.
n => f (n) => f (f (n)) => f (f (f (n))) => f (f (f (f (n)))) => ...
이 질문 은 주장 f(f(n)) = -n을 f부정하는 두 개의 연속적인 적용을 요구 합니다. f총 4 개의 추가 적용은 다시 항복하는 주장을 부정 n합니다.
n => f (n) => -n => f (f (f (n))) => n => f (n) => ...
이제 길이 4의 명백한주기가 있습니다. x = f(n)얻은 방정식이 f(f(f(n))) = f(f(x)) = -x유지 된다는 것을 대체 하고 주목 하면 다음과 같이 산출됩니다.
n => x => -n => -x => n => ...
그래서 우리는 2 개의 숫자와 2 개의 숫자가 부정 된 길이 4의주기를 얻습니다. 순환을 직사각형으로 상상하면 부정 된 값은 반대쪽 모서리에 있습니다.
이러한 순환을 구성하는 많은 솔루션 중 하나는 n에서 시작하는 다음과 같습니다.
n => 1을 부정하고 빼기 -n-1 =-(n + 1) => 하나 추가 -n => 부정하고 하나 추가 n + 1 => 1 빼기 엔
이러한주기의 구체적인 예는입니다 +1 => -2 => -1 => +2 => +1. 거의 완료되었습니다. 생성 된주기가 홀수 양수, 짝수 후 행자 및 두 수 모두 음수를 포함하고 있다는 점에 유의하면 정수를 이러한주기 ( 2^324의 배수) 로 쉽게 분할 할 수 있으며 조건을 충족하는 함수를 찾았습니다.
그러나 우리는 0이라는 문제가 있습니다. 0 => x => 00이 그 자체로 부정되기 때문에 순환이 포함되어야합니다 . 그리고주기는 이미 0 => x다음과 같다고 말하고 있기 때문 0 => x => 0 => x입니다. 이 길이는 두 가지의주기이며, x하지로, 두 응용 프로그램 후 자체에 설정되어 -x. 다행히 문제를 해결하는 한 가지 사례가 있습니다. 경우 X등호 제로 우리는 제로를 포함하는 길이 하나의 사이클을 얻고 제로의 고정 점이라고 우리는 그 문제의 결론을 해결 f.
끝난? 거의. 우리는 2^32숫자를 가지고 있고, 0은 2^32 - 1숫자를 남기는 고정 소수점 이고, 우리는 그 숫자를 4 개의 숫자로 나누어야합니다. 2^32 - 14의 배수가 아닌 나쁜 -길이 4의 어떤주기에도 3 개의 숫자가 남습니다.
나는 이르기까지 3 비트 부호 itegers의 작은 세트를 사용하여 솔루션의 나머지 부분 설명 할 것 -4을을 +3. 우리는 0으로 끝났습니다. 하나의 완전한주기가 +1 => -2 => -1 => +2 => +1있습니다. 이제에서 시작하는주기를 구성하겠습니다 +3.
+3 => -4 => -3 => +4 => +3
발생하는 문제는 +43 비트 정수로 표현할 수 없다는 것입니다. 우리 는 여전히 유효한 3 비트 정수인 것을 +4부정 -3하여 얻을 수 +3있지만 1을 +3(binary 011)에 더하면 바이너리가 생성 100됩니다. 부호없는 정수로 해석되지만 부호있는 정수 +4로 해석해야합니다 -4. 그래서, 실제로 -4이 실시 예 또는 Int.MinValue일반적인 경우는 정수 산술 부정의 제 2 고정 점 인 - 0및 Int.MinValuethemselve 매핑된다. 따라서주기는 실제로 다음과 같습니다.
+3 => -4 => -3 => -4 => -3
길이 2의주기이며 +3를 통해 추가 로주기에 들어갑니다 -4. 결과적 -4으로 두 기능 응용 프로그램 이후에 자신 +3에 올바르게 매핑되고 -3두 기능 응용 프로그램 이후에 올바르게 매핑 되지만 -3두 기능 응용 프로그램 후에는 자신에 잘못 매핑됩니다.
그래서 우리는 하나를 제외한 모든 정수에 대해 작동하는 함수를 구성했습니다. 더 잘할 수 있습니까? 아니야 우리는 할 수 없어. 왜? 길이가 4 인주기를 구성해야하며 최대 4 개의 값까지 전체 정수 범위를 포괄 할 수 있습니다. 나머지 값은 두 개의 고정 점이다 0하고 Int.MinValue그 자신과 두 개의 임의의 정수에 매핑 될 수 있어야 x하고 -x그 두 함수의 애플리케이션에 의해 서로에 매핑되어야한다.
지도하기 x로 -x하고 그 그들이 네 사이클을 형성해야하며, 그들이 그주기의 반대 모서리에 위치해야합니다 마찬가지입니다. 결과에서 0와 Int.MinValue도 반대 모서리에 있어야합니다. 이 올바르게 매핑됩니다 x하고 -x있지만, 두 개의 고정 점을 교환 0하고 Int.MinValue이 기능을 애플리케이션 후 두 실패의 입력으로 우리를 둡니다. 따라서 모든 값에 대해 작동하는 함수를 구성하는 것은 불가능하지만 하나를 제외한 모든 값에 대해 작동하는 함수가 있으며 이것이 우리가 얻을 수있는 최고입니다.
복소수를 사용하면 숫자를 부정하는 작업을 두 단계로 효과적으로 나눌 수 있습니다.
- n에 i를 곱하면 n * i가됩니다. n은 시계 반대 방향으로 90 ° 회전합니다.
- i를 다시 곱하면 -n이됩니다.
좋은 점은 특별한 처리 코드가 필요하지 않다는 것입니다. i를 곱하면됩니다.
그러나 복소수를 사용할 수 없습니다. 따라서 데이터 범위의 일부를 사용하여 어떻게 든 자신의 가상 축을 만들어야합니다. 초기 값만큼 허수 (중간) 값이 정확히 필요하므로 데이터 범위의 절반 만 남게됩니다.
서명 된 8 비트 데이터를 가정하여 다음 그림에서이를 시각화하려고했습니다. 32 비트 정수에 대해이 값을 조정해야합니다. 초기 n의 허용 범위는 -64에서 +63입니다. 다음은 양수 n에 대해 함수가하는 일입니다.
- n이 0..63 (초기 범위)에 있으면 함수 호출은 64를 추가하여 n을 64..127 (중간 범위) 범위에 매핑합니다.
- n이 64..127 (중간 범위)에 있으면 함수는 64에서 n을 빼서 n을 0 ..- 63 범위로 매핑합니다.
음수 n의 경우 함수는 중간 범위 -65 ..- 128을 사용합니다.
int.MaxValue 및 int.MinValue를 제외하고 작동합니다.
public static int f(int x)
{
if (x == 0) return 0;
if ((x % 2) != 0)
return x * -1 + (-1 *x) / (Math.Abs(x));
else
return x - x / (Math.Abs(x));
}
질문은 함수의 입력 유형과 반환 값이 무엇 f이어야 하는지에 대해 아무것도 말하지 않습니다 (적어도 당신이 제시 한 방식은 아닙니다) ...
... n이 32 비트 정수일 때 f(f(n)) = -n
그래서 어떻게
Int64 f(Int64 n)
{
return(n > Int32.MaxValue ?
-(n - 4L * Int32.MaxValue):
n + 4L * Int32.MaxValue);
}
n이 32 비트 정수이면 문 f(f(n)) == -n은 참이됩니다.
분명히이 접근 방식은 훨씬 더 넓은 범위의 숫자로 확장 될 수 있습니다.
자바 스크립트 (또는 기타 동적 유형 언어)의 경우 함수가 int 또는 객체를 받아들이고 다른 것을 반환하도록 할 수 있습니다. 즉
function f(n) {
if (n.passed) {
return -n.val;
} else {
return {val:n, passed:1};
}
}
기부
js> f(f(10))
-10
js> f(f(-10))
10
또는 강력한 형식의 언어로 오버로딩을 사용할 수 있지만 규칙을 위반할 수 있습니다.
int f(long n) {
return n;
}
long f(int n) {
return -n;
}
플랫폼에 따라 일부 언어를 사용하면 함수에서 상태를 유지할 수 있습니다. VB.Net, 예 :
Function f(ByVal n As Integer) As Integer
Static flag As Integer = -1
flag *= -1
Return n * flag
End Function
IIRC, C ++도 이것을 허용했습니다. 나는 그들이 다른 해결책을 찾고 있다고 생각합니다.
또 다른 아이디어는 함수에 대한 첫 번째 호출의 결과를 정의하지 않았기 때문에 홀수 / 균등성을 사용하여 부호 반전 여부를 제어 할 수 있다는 것입니다.
int f(int n)
{
int sign = n>=0?1:-1;
if (abs(n)%2 == 0)
return ((abs(n)+1)*sign * -1;
else
return (abs(n)-1)*sign;
}
모든 짝수의 크기에 1을 더하고 모든 홀수의 크기에서 1을 뺍니다. 두 번의 호출의 결과는 크기가 같지만 한 번의 호출은 부호를 바꿉니다. 이것이 작동하지 않는 경우 (-1, max 또는 min int)가 있지만 지금까지 제안 된 다른 것보다 훨씬 잘 작동합니다.
JavaScript 예외를 악용합니다.
function f(n) {
try {
return n();
}
catch(e) {
return function() { return -n; };
}
}
f(f(0)) => 0
f(f(1)) => -1
모든 32 비트 값의 경우 (-0이 -2147483648임을주의해야 함)
int rotate(int x)
{
static const int split = INT_MAX / 2 + 1;
static const int negativeSplit = INT_MIN / 2 + 1;
if (x == INT_MAX)
return INT_MIN;
if (x == INT_MIN)
return x + 1;
if (x >= split)
return x + 1 - INT_MIN;
if (x >= 0)
return INT_MAX - x;
if (x >= negativeSplit)
return INT_MIN - x + 1;
return split -(negativeSplit - x);
}
기본적으로 각 -x => x => -x 루프와 ay => -y => y 루프를 쌍으로 연결해야합니다. 그래서 나는 split.
예 : 4 비트 정수의 경우 :
0 => 7 => -8 => -7 => 0
1 => 6 => -1 => -6 => 1
2 => 5 => -2 => -5 => 2
3 => 4 => -3 => -4 => 3
C ++ 버전, 아마도 규칙을 약간 변경하지만 모든 숫자 유형 (floats, int, doubles) 및 단항 마이너스를 오버로드하는 클래스 유형에서도 작동합니다.
template <class T>
struct f_result
{
T value;
};
template <class T>
f_result <T> f (T n)
{
f_result <T> result = {n};
return result;
}
template <class T>
T f (f_result <T> n)
{
return -n.value;
}
void main (void)
{
int n = 45;
cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
float p = 3.14f;
cout << "f(f(" << p << ")) = " << f(f(p)) << endl;
}
x86 asm (AT & T 스타일) :
; input %edi
; output %eax
; clobbered regs: %ecx, %edx
f:
testl %edi, %edi
je .zero
movl %edi, %eax
movl $1, %ecx
movl %edi, %edx
andl $1, %eax
addl %eax, %eax
subl %eax, %ecx
xorl %eax, %eax
testl %edi, %edi
setg %al
shrl $31, %edx
subl %edx, %eax
imull %ecx, %eax
subl %eax, %edi
movl %edi, %eax
imull %ecx, %eax
.zero:
xorl %eax, %eax
ret
코드 검사, 가능한 모든 32 비트 정수 전달, -2147483647 오류 (언더 플로).
전역을 사용합니다 ...하지만 그렇게?
bool done = false
f(int n)
{
int out = n;
if(!done)
{
out = n * -1;
done = true;
}
return out;
}
이 Perl 솔루션 은 정수, 부동 소수점 및 문자열에 대해 작동합니다 .
sub f {
my $n = shift;
return ref($n) ? -$$n : \$n;
}
테스트 데이터를 사용해보십시오.
print $_, ' ', f(f($_)), "\n" for -2, 0, 1, 1.1, -3.3, 'foo' '-bar';
산출:
-2 2
0 0
1 -1
1.1 -1.1
-3.3 3.3
foo -foo
-bar +bar
아무도 f (x)가 같은 유형이어야한다고 말한 적이 없습니다.
def f(x):
if type(x) == list:
return -x[0]
return [x]
f(2) => [2]
f(f(2)) => -2
나는 실제로 문제 자체에 대한 해결책을 제시하려고하는 것이 아니지만,이 문제가 제기 된 것이 (직업?) 인터뷰의 일부라고 질문에 나와 있으므로 몇 가지 의견이 있습니다.
- 저는 먼저 "왜 그런 기능이 필요한가요? 이것이 더 큰 문제는 무엇입니까?"라고 물었습니다. 그 자리에서 실제 제기 된 문제를 해결하려고하는 대신. 이것은 내가 어떻게 생각하고 이와 같은 문제를 어떻게 해결하는지 보여줍니다. 누가 알아? 그것은 처음에 인터뷰에서 질문이 제기되는 실제 이유 일 수도 있습니다. 대답이 "괜찮습니다. 필요하다고 가정하고이 기능을 어떻게 설계할지 보여주십시오." 그런 다음 계속 그렇게 할 것입니다.
- 그런 다음 사용할 C # 테스트 케이스 코드를 작성하고 (명백한 : 루프에서
int.MinValue~까지int.MaxValue,n해당 범위의 각 호출에f(f(n))대해 결과를 확인합니다.-n) 그런 다음 테스트 주도 개발을 사용하여 이러한 함수를 얻을 것이라고 말합니다 . - 면접관이 계속해서 제기 된 문제를 해결해달라고 요청하는 경우에만 실제로 인터뷰 중에 의사 코드를 작성하여 일종의 답을 얻으려고 시도합니다. 하지만 면접관이 회사가 어떤지 알 수 있다면 그 자리에 뛰어들 것 같지는 않습니다.
아,이 답변은 인터뷰가 C # 프로그래밍 관련 직책에 대한 것이라고 가정합니다. 면접이 수학 관련 입장이라면 물론 어리석은 대답이 될 것입니다. ;-)
2 개의 가장 중요한 비트를 변경하겠습니다.
00.... => 01.... => 10.....
01.... => 10.... => 11.....
10.... => 11.... => 00.....
11.... => 00.... => 01.....
보시다시피, 그것은 단지 추가 일뿐입니다.
어떻게 답을 얻었습니까? 내 첫 번째 생각은 대칭에 대한 필요성이었습니다. 내가 시작한 곳으로 돌아가려면 4 번 돌립니다. 처음에는 2 비트 그레이 코드라고 생각했습니다. 그런 다음 실제로 표준 바이너리로 충분하다고 생각했습니다.
다음은이 문제를 해결하는 데 복소수를 사용할 수 없다는 요구 사항 또는 주장에서 영감을 얻은 솔루션입니다.
-1의 제곱근을 곱하는 것은 아이디어이며, -1은 정수에 대한 제곱근을 갖지 않기 때문에 실패한 것처럼 보입니다. 하지만 mathematica와 같은 프로그램을 가지고 놀다 보면
(1,849,436,465 2 +1) 모드 (2 32 -2) = 0.
그리고 이것은 -1의 제곱근을 갖는 것과 거의 같습니다. 함수의 결과는 부호있는 정수 여야합니다. 따라서 저는 0에 가장 가까운 x 모듈로 n에 합동하는 정수 y를 반환하는 수정 된 모듈로 연산 mods (x, n)를 사용할 것입니다. 모듈로 연산을 수행하는 프로그래밍 언어는 매우 드물지만 쉽게 정의 할 수 있습니다. . 예를 들어 파이썬에서는 다음과 같습니다.
def mods(x, n):
y = x % n
if y > n/2: y-= n
return y
위의 방정식을 사용하면 이제 문제를 다음과 같이 해결할 수 있습니다.
def f(x):
return mods(x*1849436465, 2**32-3)
이것은 f(f(x)) = -x범위의 모든 정수에 대해 만족 합니다 . 의 결과 도이 범위에 있지만 물론 계산에는 64 비트 정수가 필요합니다.[-231-2, 231-2]f(x)
2 ^ 32-1 개의 숫자 범위에 대한 C #, (Int32.MinValue)를 제외한 모든 int32 숫자
Func<int, int> f = n =>
n < 0
? (n & (1 << 30)) == (1 << 30) ? (n ^ (1 << 30)) : - (n | (1 << 30))
: (n & (1 << 30)) == (1 << 30) ? -(n ^ (1 << 30)) : (n | (1 << 30));
Console.WriteLine(f(f(Int32.MinValue + 1))); // -2147483648 + 1
for (int i = -3; i <= 3 ; i++)
Console.WriteLine(f(f(i)));
Console.WriteLine(f(f(Int32.MaxValue))); // 2147483647
인쇄물:
2147483647
3
2
1
0
-1
-2
-3
-2147483647
기본적으로이 함수는 사용 가능한 범위를 크기 4의 주기로 나누어야합니다. -n은 n주기의 반대쪽 끝에 있습니다. 그러나 0은 크기 1의주기에 속해야합니다 0->x->0->x != -x. 그렇지 않으면 . 0이 단독이므로 4 개의 요소가있는 적절한주기에 있지 않은 범위 (크기가 4의 배수)에 3 개의 다른 값이 있어야합니다.
나는 것으로 이러한 추가 이상한 값을 선택 MIN_INT, MAX_INT하고 MIN_INT+1. 또한 올바르게 MIN_INT+1매핑 MAX_INT되지만 거기에 갇혀 다시 매핑되지 않습니다. 제대로 작동하지 않는 극단적 인 값만 좋은 속성을 가지고 있기 때문에 이것이 최선의 타협이라고 생각합니다. 또한 모든 BigInt에서 작동 함을 의미합니다 .
int f(int n):
if n == 0 or n == MIN_INT or n == MAX_INT: return n
return ((Math.abs(n) mod 2) * 2 - 1) * n + Math.sign(n)
무국적이어야한다고 아무도 말하지 않았습니다.
int32 f(int32 x) {
static bool idempotent = false;
if (!idempotent) {
idempotent = true;
return -x;
} else {
return x;
}
}
부정 행위이지만 많은 예 만큼은 아닙니다. 더 나쁜 것은 호출자의 주소가 & f인지 확인하기 위해 스택을 들여다 보는 것이지만, 이것은 더 이식 가능할 것입니다 (스레드 안전은 아니지만 ... 스레드 안전 버전은 TLS를 사용합니다). 더 많은 악 :
int32 f (int32 x) {
static int32 answer = -x;
return answer;
}
물론 이들 중 어느 것도 MIN_INT32의 경우에 너무 잘 작동하지 않지만 더 넓은 유형을 반환하도록 허용되지 않는 한 할 수있는 귀중한 작업은 거의 없습니다.
31 번째 비트를 가상 ( i ) 비트로 사용하는 것이 전체 범위의 절반을 지원하는 접근 방식이라고 상상할 수 있습니다.
n = [0 .. 2 ^ 31-1]에서 작동
int f(int n) {
if (n & (1 << 31)) // highest bit set?
return -(n & ~(1 << 31)); // return negative of original n
else
return n | (1 << 31); // return n with highest bit set
}
문제는 "32 비트 부호있는 정수"라고 표시되지만 2s 보수 인지 1s 보수 인지는 지정하지 않습니다 .
1의 보수를 사용하면 모든 2 ^ 32 값이 길이 4의 주기로 발생합니다. 0에 대한 특별한 경우가 필요하지 않으며 조건문도 필요하지 않습니다.
C에서 :
int32_t f(int32_t x)
{
return (((x & 0xFFFFU) << 16) | ((x & 0xFFFF0000U) >> 16)) ^ 0xFFFFU;
}
이것은 작동합니다
- 상위 및 하위 16 비트 블록 교환
- 블록 중 하나 반전
두 번의 패스 후 우리는 원래 값의 비트 역수를 갖게됩니다. 1의 보수 표현에서 부정과 동일합니다.
예 :
Pass | x
-----+-------------------
0 | 00000001 (+1)
1 | 0001FFFF (+131071)
2 | FFFFFFFE (-1)
3 | FFFE0000 (-131071)
4 | 00000001 (+1)
Pass | x
-----+-------------------
0 | 00000000 (+0)
1 | 0000FFFF (+65535)
2 | FFFFFFFF (-0)
3 | FFFF0000 (-65535)
4 | 00000000 (+0)
:디
boolean inner = true;
int f(int input) {
if(inner) {
inner = false;
return input;
} else {
inner = true;
return -input;
}
}
return x ^ ((x%2) ? 1 : -INT_MAX);
수학자로서이 흥미로운 문제에 대한 나의 관점을 공유하고 싶습니다. 가장 효율적인 솔루션이 있다고 생각합니다.
내가 올바르게 기억한다면 첫 번째 비트를 뒤집어 부호있는 32 비트 정수를 부정합니다. 예를 들어 n = 1001 1101 1110 1011 1110 0000 1110 1010이면 -n = 0001 1101 1110 1011 1110 0000 1110 1010입니다.
그렇다면 부호있는 32 비트 정수를 받고 또 다른 부호있는 32 비트 정수를 반환하는 함수 f를 정의하는 방법은 f를 두 번받는 것이 첫 번째 비트를 뒤집는 것과 같다는 속성과 같습니다.
정수와 같은 산술 개념을 언급하지 않고 질문을 다시 말하겠습니다.
0과 길이가 32 인 1의 시퀀스를 취하고 동일한 길이의 0과 1의 시퀀스를 반환하는 함수 f를 어떻게 정의 할 수 있습니까? f를 두 번 취하는 것은 첫 번째 비트를 뒤집는 것과 같습니다.
관찰 : 32 비트 케이스에 대해 위의 질문에 답할 수 있다면 64 비트 케이스, 100 비트 케이스 등에 대해서도 답할 수 있습니다. 처음 32 비트에 f를 적용하면됩니다.
이제 2 비트 케이스에 대한 질문에 답할 수 있다면 Voila!
그리고 예, 처음 2 비트를 변경하는 것으로 충분합니다.
다음은 의사 코드입니다.
1. take n, which is a signed 32-bit integer.
2. swap the first bit and the second bit.
3. flip the first bit.
4. return the result.
비고 : 2 단계와 3 단계는 함께 (a, b)-> (-b, a)로 합산 할 수 있습니다. 익숙해 보입니까? 그러면 평면의 90도 회전과 제곱근 -1의 곱셈이 생각 나게됩니다.
긴 서곡없이 의사 코드 만 제시하면 모자에서 토끼처럼 보일 것입니다. 어떻게 해결책을 얻었는지 설명하고 싶었습니다.
참고 URL : https://stackoverflow.com/questions/731832/designing-function-ffn-n
'Program Tip' 카테고리의 다른 글
| PostgreSQL 사용자 비밀번호를 변경하는 방법은 무엇입니까? (0) | 2020.09.28 |
|---|---|
| JavaScript에서 나머지로 정수 나누기? (0) | 2020.09.28 |
| ThreadLocal 변수는 언제 어떻게 사용해야합니까? (0) | 2020.09.28 |
| 오류 : vcvarsall.bat를 찾을 수 없습니다. (0) | 2020.09.28 |
| 컬렉션이 수정되었습니다. (0) | 2020.09.28 |