Merancang fungsi f (f (n)) == -n

841

Sebuah pertanyaan yang saya dapatkan pada wawancara terakhir saya:

Desain suatu fungsi f, sedemikian rupa sehingga:

f(f(n)) == -n

Di mana integer bertandan 32 bit ; Anda tidak dapat menggunakan aritmatika bilangan kompleks.

Jika Anda tidak dapat mendesain fungsi seperti itu untuk seluruh jajaran angka, rancanglah untuk rentang semaksimal mungkin.

Ada ide?

Gumbo
sumber
2
Untuk apa pekerjaan wawancara ini?
tymtam

Jawaban:

377

Bagaimana tentang:

f (n) = tanda (n) - (-1) n * n

Dengan 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)

Python secara otomatis mempromosikan bilangan bulat ke panjang sewenang-wenang. Dalam bahasa lain, bilangan bulat positif terbesar akan meluap, sehingga bilangan bulat akan berfungsi untuk semua bilangan bulat kecuali yang itu.


Untuk membuatnya berfungsi untuk bilangan real, Anda harus mengganti n in (-1) n dengan { ceiling(n) if n>0; floor(n) if n<0 }.

Di C # (berfungsi untuk sembarang ganda, kecuali dalam situasi luapan):

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));
}
RossFabricant
sumber
10
Rusak untuk -1, karena -1 * 0 masih 0
Joel Coehoorn
3
Bukan itu. f (-1) = 0. f (0) = 1
1800 INFORMASI
5
Namun rusak untuk 1. f (1) = 0. f (0) = 1
1800 INFORMASI
18
Hmm, menyimpan keadaan dengan angka genap dan ganjil, aku seharusnya sudah memikirkan itu.
Tidak diketahui
38
Saya pikir hal yang paling penting bukanlah fungsi sebenarnya (ada banyak solusi tak terhingga), tetapi proses di mana Anda dapat membangun fungsi seperti itu.
pyon
440

Anda tidak mengatakan bahasa apa yang mereka harapkan ... Ini solusi statis (Haskell). Ini pada dasarnya mengacaukan 2 bit paling signifikan:

f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30
    | otherwise = complementBit x 30

Jauh lebih mudah dalam bahasa dinamis (Python). Periksa apakah argumennya adalah angka X dan kembalikan lambda yang mengembalikan -X:

def f(x):
   if isinstance(x,int):
      return (lambda: -x)
   else:
      return x()
viraptor
sumber
23
Keren, saya suka ini ... pendekatan yang sama dalam JavaScript: var f = function (n) {return (typeof n == 'function')? n (): function () {return -n; }}
Mark Renouf
Mungkin saja Haskell saya sangat berkarat, tetapi sudahkah Anda memeriksanya untuk (f 0)? Sepertinya itu harus menghasilkan hasil yang sama seperti (f 0x80000000), setidaknya jika kita berurusan dengan int 32-bit dengan aritmatika sampul (pada operasi negate). Dan itu akan buruk.
Darius Bacon
11
Akan pewawancara rata-rata bahkan tahu apa lambda membangun adalah ?
Jeremy Powell
4
Tentu saja, seperti trik tipe-kecurangan juga bekerja di Haskell, meskipun itu statis: class C a b | a->b where { f :: a->b }; instance C Int (()->Int) where { f=const.negate }; instance C (()->Int) Int where { f=($()) }.
leftaroundtentang
4
Apa? Dari mana Anda mendapatkan gagasan bahwa typeof f (n) === 'function', khususnya, di mana n adalah angka dan Anda mengharapkan angka dikembalikan? Saya tidak mengerti bagaimana contoh kasus berlaku di sini. Saya tidak berbicara Python dengan baik, tetapi dalam argumen memeriksa JS untuk jenis fungsi jelas salah dalam kasus ini. Hanya solusi numerik yang berlaku di sini. f adalah fungsi, f (n) adalah angka.
Harry
284

Berikut adalah bukti mengapa fungsi semacam itu tidak ada, untuk semua angka, jika tidak menggunakan informasi tambahan (kecuali 32 bit int):

Kita harus memiliki f (0) = 0. (Bukti: Misalkan f (0) = x. Kemudian f (x) = f (f (0)) = -0 = 0. Sekarang, -x = f (f (x (x) )) = f (0) = x, yang berarti bahwa x = 0.)

Selanjutnya, untuk apa pun xdan y, misalkan f(x) = y. Kami menginginkannya f(y) = -x. Dan f(f(y)) = -y => f(-x) = -y. Untuk meringkas: jika f(x) = y, maka f(-x) = -y, dan f(y) = -x, dan f(-y) = x.

Jadi, kita perlu membagi semua bilangan bulat kecuali 0 ke dalam set 4, tetapi kami memiliki jumlah ganjil dari bilangan bulat tersebut; tidak hanya itu, jika kita menghapus bilangan bulat yang tidak memiliki pasangan positif, kita masih memiliki 2 (mod4) angka.

Jika kita menghapus 2 angka maksimal yang tersisa (berdasarkan nilai abs), kita bisa mendapatkan fungsinya:

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);
    }
}   

Tentu saja pilihan lain, adalah tidak mematuhi 0, dan mendapatkan 2 angka yang kami hapus sebagai bonus. (Tapi itu konyol jika.)

SurDin
sumber
29
Saya tidak percaya saya harus membaca sejauh ini untuk menemukan solusi prosedural yang baik yang menangani angka negatif tanpa menggunakan variabel global atau trik yang mengaburkan kode. Jika saya dapat memilih Anda lebih dari satu kali, saya akan melakukannya.
Kyle Simek
Bagus pengamatan, bahwa ada ganjil bilangan bulat nol di setiap n ditandatangani bit.
Andres Jaan Tack
Ini akan menjadi jawaban saya juga, tetapi waspadai kasus tepi n = -2147483648(nilai minimum); Anda tidak dapat abs(n)dalam hal itu, dan hasilnya akan tidak ditentukan (atau pengecualian).
Kirk Broadhurst
1
@ a1kmm: Maaf, -2³² di atas seharusnya -2³¹. Bagaimanapun, kasus di mana f (0) ≠ 0 (dan juga f (0) = - 2³¹) sebenarnya adalah kasus yang lebih mudah, karena kami menunjukkan keduanya terputus dari yang lain. Kasus lain yang perlu kita pertimbangkan adalah bahwa f (0) = 0, tetapi f (x) = - 2³¹ untuk beberapa x ≠ 0, x ≠ -2³¹. Dalam hal ini, f (-2³¹) = f (f (x)) = - x (note -x tidak bisa menjadi -2³¹, karena tidak ada x seperti itu ada). Selanjutnya biarkan f (-x) = y. Kemudian f (y) = f (f (-x)) = x. Sekali lagi y tidak bisa -2³¹ (seperti f (y) = x, tetapi f (-2³¹) = - x, dan x bukan 0). Jadi, -2³¹ = f (x) = f (f (y)) = - y, yang tidak mungkin. Jadi memang 0 dan -2³¹ harus diputuskan dari yang lain (bukan gambar dari hal lain).
ShreevatsaR
1
@will Tidak ada nol yang ditandatangani, jika (seperti yang saya asumsikan) kita sedang berbicara tentang bilangan bulat 32-bit pelengkap dua.
goffrie
146

Berkat kelebihan muatan di 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));
}
Comptrol
sumber
4
Sayangnya, karena nama mangling, fungsi yang Anda sebut "f" sebenarnya memiliki nama yang lebih aneh.
pyon
1
Saya sudah memikirkan sesuatu seperti itu, tetapi berpikir dalam C, ini dibuang ... kerja bagus!
Liran Orevi
@Rui Craverio: Tidak akan berfungsi di .NET 3.5+ karena penulis memilih untuk menggunakan kata kunci var sebagai nama variabel.
Kredns
72
secara teknis ... ini bukan yang diminta pertanyaan. Anda mendefinisikan 2 fungsi f (), f (int) dan f (float) dan pertanyaan bertanya "Desain fungsi f () ..."
elcuco
2
@elcuco Secara teknis, tentu saja, tetapi secara logis itu adalah satu fungsi dengan banyak kelebihan (Anda dapat melakukan f (f (42)) dengan itu). Karena definisi tidak mengatakan apa-apa tentang parameter dan nilai pengembalian, saya hampir tidak dapat menerimanya sebagai definisi teknis.
Marek Toman
135

Atau, Anda dapat menyalahgunakan preprosesor:

#define f(n) (f##n)
#define ff(n) -n

int main()
{
  int n = -42;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}
Skizz
sumber
Jadi Anda akan menjadi Konrad "Le Chiffre" Rudolph? Saya akan mengambil mantel saya. Ya, saya tahu tentang keseluruhan "void main", tetapi menambahkan "return 0;" adalah begitu banyak usaha ekstra ;-)
Skizz
25
@ Skizz, kembali 0 dari main tidak diperlukan di c ++ bahkan dengan nilai pengembalian int ... jadi dengan melakukannya dengan benar Anda benar-benar mengetik satu karakter kurang!
Dan Olson
10
Skizz selalu menyalahgunakan preprosesor: D
Arnis Lapsa
23
Ini bukan fungsi ..jadi ini bukan solusi yang valid
smerlin
3
@smerlin: Secara teknis fungsi inline mengembalikan fungsi inline: tubuh keduanya diperluas pada waktu kompilasi, atau lebih tepatnya sebelum. Tidak bisa lebih efisien dari ini.
Jon Purdy
103

Ini berlaku untuk semua angka negatif.

    f (n) = abs (n)

Karena ada satu angka lebih negatif daripada angka positif untuk dua integer komplemen, f(n) = abs(n)valid untuk satu kasus lebih dari f(n) = n > 0 ? -n : nsolusi yang sama dengan f(n) = -abs(n). Punya satu per satu ...: D

MEMPERBARUI

Tidak, itu tidak berlaku untuk satu kasus lagi karena saya baru saja dikenali oleh komentar litb ... abs(Int.Min)hanya akan meluap ...

Saya berpikir tentang menggunakan informasi mod 2 juga, tetapi menyimpulkan, itu tidak berfungsi ... untuk awal. Jika dilakukan dengan benar, ini akan berfungsi untuk semua angka kecuali Int.Minkarena ini akan meluap.

MEMPERBARUI

Saya bermain dengannya sebentar, mencari trik manipulasi bit yang bagus, tetapi saya tidak dapat menemukan satu-liner yang bagus, sedangkan solusi mod 2 cocok untuk satu.

    f (n) = 2n (abs (n)% 2) - n + sgn (n)

Di C #, ini menjadi yang berikut:

public static Int32 f(Int32 n)
{
    return 2 * n * (Math.Abs(n) % 2) - n + Math.Sign(n);
}

Untuk membuatnya berfungsi untuk semua nilai, Anda harus mengganti Math.Abs()dengan (n > 0) ? +n : -ndan memasukkan perhitungan dalam satu uncheckedblok. Kemudian Anda bahkan Int.Mindipetakan ke dirinya sendiri seperti halnya negasi yang tidak terkendali.

MEMPERBARUI

Terinspirasi oleh jawaban lain saya akan menjelaskan bagaimana fungsi bekerja dan bagaimana membangun fungsi seperti itu.

Mari kita mulai dari awal. Fungsi fini berulang kali diterapkan pada nilai yang diberikan nmenghasilkan urutan nilai.

    n => f (n) => f (f (n)) => f (f (f (n)))) => f (f (f (f (f (n)))))) => ...

Pertanyaannya menuntut f(f(n)) = -n, yaitu dua aplikasi berturut-turut fmeniadakan argumen. Dua aplikasi lebih lanjut dari f- total empat - meniadakan argumen lagi menghasilkan nlagi.

    n => f (n) => -n => f (f (f (n))) => n => f (n) => ...

Sekarang ada siklus panjang empat yang jelas. Mengganti x = f(n)dan mencatat bahwa persamaan yang diperoleh f(f(f(n))) = f(f(x)) = -xberlaku, menghasilkan yang berikut.

    n => x => -n => -x => n => ...

Jadi kita mendapatkan siklus panjang empat dengan dua angka dan dua angka dinegasikan. Jika Anda membayangkan siklus sebagai persegi panjang, nilai yang dinegasikan terletak di sudut yang berlawanan.

Salah satu solusi untuk membangun siklus seperti itu adalah yang berikut dimulai dari n.

 n => meniadakan dan kurangi satu
-n - 1 = - (n +1) => tambahkan satu
-n => negate dan tambahkan satu
 n +1 => kurangi satu
 n

Contoh konkret dari siklus semacam itu adalah +1 => -2 => -1 => +2 => +1. Kami hampir selesai. Memperhatikan bahwa siklus yang dikonstruksi mengandung bilangan positif ganjil, bahkan penggantinya, dan kedua bilangan tersebut meniadakan, kita dapat dengan mudah mempartisi bilangan bulat menjadi banyak siklus semacam itu ( 2^32merupakan kelipatan empat) dan telah menemukan fungsi yang memenuhi kondisi.

Tetapi kami memiliki masalah dengan nol. Siklus harus mengandung 0 => x => 0karena nol dinegasikan ke dirinya sendiri. Dan karena siklus menyatakan sudah 0 => xmengikuti 0 => x => 0 => x. Ini hanya siklus panjang dua dan xdiubah menjadi dirinya sendiri setelah dua aplikasi, bukan menjadi -x. Untungnya ada satu kasus yang menyelesaikan masalah. Jika Xsama dengan nol kita memperoleh siklus panjang yang hanya mengandung nol dan kita memecahkan masalah itu dengan menyimpulkan bahwa nol adalah titik tetap f.

Selesai? Hampir. Kami memiliki 2^32angka, nol adalah angka tetap yang meninggalkan titik 2^32 - 1, dan kami harus mempartisi angka itu menjadi siklus empat angka. Buruk itu 2^32 - 1bukan kelipatan empat - akan tetap ada tiga angka tidak dalam siklus dengan panjang empat.

Saya akan menjelaskan bagian yang tersisa dari solusi menggunakan set yang lebih kecil dari 3 bit yang ditandatangani mulai dari -4ke +3. Kita selesai dengan nol. Kami memiliki satu siklus lengkap +1 => -2 => -1 => +2 => +1. Sekarang mari kita buat siklus mulai dari +3.

    +3 => -4 => -3 => +4 => +3

Masalah yang muncul adalah yang +4tidak direpresentasikan sebagai integer 3 bit. Kami akan memperoleh +4dengan meniadakan -3ke +3- apa yang masih merupakan integer 3 bit yang valid - tetapi kemudian menambahkan satu ke +3(biner 011) menghasilkan 100biner. Ditafsirkan sebagai bilangan bulat yang tidak ditandatangani, +4tetapi kita harus menafsirkannya sebagai bilangan bulat yang ditandatangani -4. Jadi sebenarnya -4untuk contoh ini atau Int.MinValuedalam kasus umum adalah titik tetap kedua negasi aritmatika bilangan bulat - 0 dan Int.MinValuedipetakan ke mereka sendiri. Jadi siklusnya sebenarnya sebagai berikut.

    +3 => -4 => -3 => -4 => -3

Ini adalah siklus dengan panjang dua dan juga +3memasuki siklus melalui -4. Karena -4itu dipetakan dengan benar ke dirinya sendiri setelah dua aplikasi fungsi, +3dipetakan dengan benar ke -3setelah dua aplikasi fungsi, tetapi -3dipetakan secara keliru ke dirinya sendiri setelah dua aplikasi fungsi.

Jadi kami membangun fungsi yang bekerja untuk semua bilangan bulat kecuali satu. Bisakah kita berbuat lebih baik? Tidak, kita tidak bisa. Mengapa? Kita harus membuat siklus dengan panjang empat dan mampu mencakup seluruh rentang integer hingga empat nilai. Nilai yang tersisa adalah dua titik tetap 0dan Int.MinValueyang harus dipetakan untuk diri mereka sendiri dan dua bilangan bulat sewenang-wenang xdan -xyang harus dipetakan satu sama lain oleh dua aplikasi fungsi.

Untuk memetakan xke -xdan sebaliknya mereka harus membentuk empat siklus dan mereka harus berada di sudut yang berlawanan dari siklus itu. Karena itu 0dan Int.MinValueharus berada di sudut yang berlawanan juga. Ini akan memetakan dengan benar xdan -xtetapi menukar dua titik tetap 0dan Int.MinValuesetelah dua aplikasi fungsi dan meninggalkan kita dengan dua input yang gagal. Jadi tidak mungkin untuk membangun fungsi yang bekerja untuk semua nilai, tetapi kami memiliki satu yang berfungsi untuk semua nilai kecuali satu dan ini adalah yang terbaik yang bisa kami capai.

Daniel Brückner
sumber
Tidak memenuhi kriteria: abs (abs (n))! = -N
Dan Olson
Tentu saja, untuk semua angka negatif, seperti katanya. Itu adalah bagian dari pertanyaan: Jika Anda tidak dapat membuat yang umum, buatlah yang cocok untuk jangkauan seluas mungkin.
jalf
Jawaban ini setidaknya sama baiknya sebagai jawaban oleh Marj Synowiec dan Rowland Shaw, hanya bekerja untuk berbagai berbeda nomor
1800 INFORMATION
19
Bung, Anda mungkin juga menyingkirkan "PEMBARUAN" dan hanya menulis satu jawaban yang benar kohesif. Bagian bawah 3/4 ("terinspirasi oleh jawaban lain") mengagumkan.
Andres Jaan Tack
1
Saya sangat suka solusi abs untuk angka negatif. Sederhana dan mudah dimengerti.
Thorbjørn Ravn Andersen
97

Menggunakan bilangan kompleks, Anda dapat secara efektif membagi tugas meniadakan angka menjadi dua langkah:

  • kalikan n dengan i, dan Anda mendapatkan n * i, yang diputar 90 ° berlawanan arah jarum jam
  • kalikan lagi dengan saya, dan Anda mendapatkan -n

Yang hebat adalah Anda tidak memerlukan kode penanganan khusus. Hanya mengalikan dengan saya melakukan pekerjaan.

Tapi Anda tidak diizinkan menggunakan angka kompleks. Jadi Anda harus entah bagaimana membuat sumbu imajiner Anda sendiri, menggunakan bagian dari rentang data Anda. Karena Anda membutuhkan nilai imajiner (menengah) persis seperti nilai awal, Anda hanya memiliki separuh rentang data.

Saya mencoba memvisualisasikan ini pada gambar berikut, dengan asumsi data 8-bit yang ditandatangani. Anda harus skala ini untuk bilangan bulat 32-bit. Kisaran yang diizinkan untuk awal n adalah -64 hingga +63. Inilah yang fungsinya untuk n positif:

  • Jika n ada di 0..63 (rentang awal), pemanggilan fungsi menambah 64, memetakan n ke kisaran 64..127 (rentang menengah)
  • Jika n berada di 64..127 (rentang menengah), fungsi mengurangi n dari 64, memetakan n ke kisaran 0 ..- 63

Untuk n negatif, fungsi ini menggunakan rentang menengah -65 ..- 128.

teks alternatif

geschema
sumber
4
@geschema, alat apa yang Anda gunakan untuk membuat grafik yang bagus?
jwfearn
10
Maaf, pertanyaannya mengatakan secara eksplisit tidak ada bilangan kompleks.
Rui Craveiro
6
@ Liran: Saya menggunakan OmniGraffle (hanya Mac)
geschema
39
+1 Saya pikir ini adalah jawaban terbaik. Saya tidak berpikir orang membaca cukup, karena mereka semua mencatat bahwa pertanyaan mengatakan bilangan kompleks tidak dapat digunakan. Saya membaca semuanya, dan Anda menjelaskan solusinya dalam bilangan kompleks untuk mengatur tahapan untuk solusi non-kompleks untuk pertanyaan yang diajukan. Dilakukan dengan sangat baik.
jrista
1
@jrista semua solusi menggunakan dimensi kedua, yaitu 'bilangan kompleks' sebenarnya (kebanyakan menggunakan ganjil vs genap, & penggunaan di atas floatvs int). 'Cincin elemen 4' yang dijelaskan oleh banyak jawaban mengharuskan 4 status, yang dapat direpresentasikan sebagai 2 dimensi masing-masing dengan 2 status. The masalah dengan jawaban ini adalah bahwa hal itu membutuhkan ruang pengolahan tambahan (hanya 'karya' untuk -64..63, namun kebutuhan -128..127 ruang) dan tidak secara eksplisit menyatakan rumus ditulis!
Kirk Broadhurst
65

Berfungsi kecuali int.MaxValue dan 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));
    }

bergambar

Rodrick Chapman
sumber
Tidak yakin mengapa ini diturunkan. Untuk input apa gagal?
Rodrick Chapman
Mengapa Anda tidak menggunakan fungsi signum?!?
comonad
1
Gambarnya sangat bagus. Kirim 0ke 0dan -2147483648ke -2147483648karena kedua angka ini adalah titik tetap untuk operator negasi x => -x,. Untuk sisa angka, ikuti panah pada gambar di atas. Seperti yang jelas dari jawaban SurDin dan komentarnya, akan ada dua angka, dalam hal ini 2147483647dan -2147483647tanpa pasangan yang tersisa untuk bertukar.
Jeppe Stig Nielsen
Itu terlihat seperti smiley - dengan banyak kerutan
Anshul
48

Pertanyaannya tidak mengatakan apa-apa tentang apa jenis input dan nilai balik fungsi fharus (setidaknya bukan cara Anda mempresentasikannya) ...

... Hanya saja ketika n adalah bilangan bulat 32-bit lalu f(f(n)) = -n

Jadi, bagaimana dengan sesuatu seperti

Int64 f(Int64 n)
{
    return(n > Int32.MaxValue ? 
        -(n - 4L * Int32.MaxValue):
        n + 4L * Int32.MaxValue);
}

Jika n adalah bilangan bulat 32-bit maka pernyataan itu f(f(n)) == -nakan benar.

Jelas, pendekatan ini dapat diperluas untuk bekerja untuk rentang nomor yang lebih luas ...

Daniel LeCheminant
sumber
2
Sneaky. Batas karakter.
Joe Phillips
2
Ya, saya sedang mengerjakan pendekatan yang sama. Anda mengalahkan saya untuk itu. +1 :)
jalf
1
Sangat pintar! Ini sangat dekat dengan (& efektif sama dengan) menggunakan bilangan kompleks, yang akan menjadi solusi yang jelas & ideal tetapi secara eksplisit tidak diizinkan. Bekerja di luar kisaran angka yang diperbolehkan.
Kirk Broadhurst
48

untuk javascript (atau bahasa yang diketik secara dinamis lainnya) Anda dapat memiliki fungsi menerima int atau objek dan mengembalikan yang lain. yaitu

function f(n) {
    if (n.passed) {
        return -n.val;
    } else {
        return {val:n, passed:1};
    }
}

memberi

js> f(f(10))  
-10
js> f(f(-10))
10

atau Anda dapat menggunakan overloading dalam bahasa yang sangat diketik meskipun itu bisa melanggar aturan yaitu

int f(long n) {
    return n;
}

long f(int n) {
    return -n;
}
cobbal
sumber
Yang terakhir tidak berarti persyaratan fungsi "a" (tunggal). :)
Drew
Hapus bagian kedua dari jawaban dan ini adalah jawaban yang benar.
jmucchiello
@Rew. Itulah sebabnya saya menyebutkan bahwa itu mungkin melanggar aturan
cobbal
2
Dalam JavaScript, fungsi adalah objek dan karenanya dapat mempertahankan status.
Nosredna
1
IMO: function f (n) {return n.passed? -n.val: {val: n, berlalu: 1}} lebih mudah dibaca dan lebih pendek.
SamGoody
46

Bergantung pada platform Anda, beberapa bahasa memungkinkan Anda menjaga status dalam fungsi. VB.Net, misalnya:

Function f(ByVal n As Integer) As Integer
    Static flag As Integer = -1
    flag *= -1

    Return n * flag
End Function

IIRC, C ++ mengizinkan ini juga. Saya curiga mereka mencari solusi yang berbeda.

Gagasan lain adalah karena mereka tidak menentukan hasil dari panggilan pertama ke fungsi, Anda bisa menggunakan keanehan untuk mengontrol apakah akan membalikkan tanda:

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;
}

Tambahkan satu ke besarnya semua angka genap, kurangi satu dari besarnya semua angka ganjil. Hasil dari dua panggilan memiliki besaran yang sama, tetapi satu panggilan di mana itu bahkan kita menukar tandanya. Ada beberapa kasus di mana ini tidak akan berhasil (-1, maks atau int min), tetapi ini bekerja jauh lebih baik daripada apa pun yang disarankan sejauh ini.

Joel Coehoorn
sumber
1
Saya percaya ini berfungsi untuk MAX_INT karena itu selalu aneh. Tidak berfungsi untuk MIN_INT dan -1.
Airsource Ltd
9
Ini bukan fungsi jika memiliki efek samping.
nos
12
Itu mungkin benar dalam matematika, tetapi tidak relevan dalam pemrograman. Jadi pertanyaannya adalah apakah mereka mencari solusi matematika atau solusi pemrograman. Tetapi mengingat bahwa itu untuk pekerjaan pemrograman ...
Ryan Lundy
+1 Saya akan memposting satu dengan C dengan "static int x" menerapkan FIFO dengan negasi dari output. Tapi ini cukup dekat.
phkahler
2
@nos: Ya, itu tidak transparan secara referensial.
Clark Gaebel
26

Memanfaatkan pengecualian JavaScript.

function f(n) {
    try {
        return n();
    }
    catch(e) { 
        return function() { return -n; };
    }
}

f(f(0)) => 0

f(f(1)) => -1

Anurag
sumber
Saya ragu pengecualian telah digunakan seperti ini sebelumnya ... :)
NoBugs
+1 Di luar kotak berpikir. Keren! Tetapi dalam kode produksi saya akan menggunakan typeof hanya untuk aman.
21

Untuk semua nilai 32-bit (dengan peringatan bahwa -0 adalah -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);
}

Anda pada dasarnya perlu memasangkan setiap -x => x => -x loop dengan ay => -y => y loop. Jadi saya memasangkan sisi yang berlawanan split.

mis. Untuk bilangan bulat 4 bit:

0 => 7 => -8 => -7 => 0
1 => 6 => -1 => -6 => 1
2 => 5 => -2 => -5 => 2
3 => 4 => -3 => -4 => 3
Eclipse
sumber
21

Versi C ++, mungkin sedikit menekuk aturan tetapi berfungsi untuk semua tipe numerik (float, ints, doubles) dan bahkan tipe kelas yang membebani minus unary:

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;
}
Skizz
sumber
Ide bagus. Sebagai alternatif, Anda mungkin bisa kehilangan struct dan bukannya memiliki satu fungsi mengembalikan pointer, fungsi lain dereference dan meniadakan.
Imbue
20

x86 asm (gaya 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

Kode diperiksa, semua bilangan bulat 32bit yang mungkin terlewati, kesalahan dengan -2147483647 (underflow).

LiraNuna
sumber
19

Menggunakan global ... tapi begitu?

bool done = false
f(int n)
{
  int out = n;
  if(!done)
  {  
      out = n * -1;
      done = true;
   }
   return out;
}
teeks99
sumber
3
Tidak yakin bahwa ini adalah maksud dari penanya pertanyaan, tetapi +1 untuk "berpikir di luar kotak".
Liran Orevi
5
Daripada mengatakan "selesai = benar" secara kondisional, Anda harus selalu mengatakan "selesai =! Selesai", dengan begitu fungsi Anda dapat digunakan lebih dari sekali.
Chris Lutz
@ Chris, karena pengaturan dilakukan ke true ada di dalam blok if (! Done), itu setara dengan done =! Done, tapi! Done tidak perlu dihitung (atau dioptimalkan oleh kompiler, jika cukup pintar) .
nsayer
1
Pikiran pertama saya adalah untuk menyelesaikan ini dengan menggunakan variabel global, meskipun rasanya seperti curang untuk pertanyaan khusus ini. Namun saya berpendapat bahwa solusi variabel global adalah solusi terbaik mengingat spesifikasi dalam pertanyaan. Menggunakan global membuatnya sangat mudah untuk memahami apa yang terjadi. Saya akan setuju bahwa selesai! = Dilakukan akan lebih baik. Pindahkan saja itu di luar klausa if.
Alderath
3
Secara teknis, apa pun yang mempertahankan status bukanlah fungsi, melainkan mesin status. Menurut definisi , fungsi selalu memberikan output yang sama untuk input yang sama.
Ted Hopp
19

Solusi Perl ini berfungsi untuk bilangan bulat, pelampung, dan string .

sub f {
    my $n = shift;
    return ref($n) ? -$$n : \$n;
}

Coba beberapa data uji.

print $_, ' ', f(f($_)), "\n" for -2, 0, 1, 1.1, -3.3, 'foo' '-bar';

Keluaran:

-2 2
0 0
1 -1
1.1 -1.1
-3.3 3.3
foo -foo
-bar +bar
FMc
sumber
Tapi itu tidak membuatnya menjadi int. Anda pada dasarnya menyimpan data variabel global di int "n" itu sendiri ... kecuali itu bukan int kalau tidak Anda tidak bisa melakukan itu. Sebagai contoh jika nadalah string saya bisa membuat 548 menjadi "First_Time_548" dan kemudian waktu berikutnya menjalankan fungsi ... if (awalan == First_Time_ ") ganti" First_Time_ "dengan" - "
Albert Renshaw
@AlbertRenshaw Tidak yakin dari mana Anda mendapatkan ide-ide itu. (1) Jelas tidak ada variabel global yang terlibat di sini. (2) Jika Anda memberikan fungsi int, Anda akan mendapatkan int kembali - atau referensi ke int, jika Anda menyebut fungsi tersebut ganjil beberapa kali. (3) Mungkin yang paling mendasar, ini Perl . Untuk semua tujuan praktis, int dan string sepenuhnya dipertukarkan. String yang seperti terlihat seperti angka akan berfungsi dengan baik sebagai angka dalam sebagian besar konteks, dan angka akan dengan senang hati meregang kapan pun diminta.
FMc
Maaf saya tidak tahu banyak perl sepertinya Anda menggunakan array global haha
Albert Renshaw
18

Tidak ada yang pernah mengatakan f (x) harus bertipe sama.

def f(x):
    if type(x) == list:
        return -x[0]
    return [x]


f(2) => [2]
f(f(2)) => -2
Tekan Z
sumber
16

Saya tidak benar-benar mencoba memberikan solusi untuk masalah itu sendiri, tetapi memiliki beberapa komentar, karena pertanyaan menyatakan masalah ini diajukan adalah bagian dari wawancara (pekerjaan?):

  • Pertama-tama saya akan bertanya, "Mengapa fungsi seperti itu dibutuhkan? Apa masalah yang lebih besar dari ini?" alih-alih mencoba memecahkan masalah yang ditimbulkan langsung di tempat. Ini menunjukkan bagaimana saya berpikir dan bagaimana saya mengatasi masalah seperti ini. Siapa tau? Itu bahkan mungkin menjadi alasan sebenarnya pertanyaan itu ditanyakan dalam sebuah wawancara. Jika jawabannya "Tidak apa-apa, anggap itu perlu, dan tunjukkan kepada saya bagaimana Anda akan merancang fungsi ini." Saya kemudian akan terus melakukannya.
  • Kemudian, saya akan menulis kode kasus uji C # yang akan saya gunakan (yang jelas: loop dari int.MinValueke int.MaxValue, dan untuk masing-masing ndalam rentang panggilan f(f(n))dan memeriksa hasilnya -n), mengatakan saya kemudian akan menggunakan Test Driven Development untuk mendapatkan fungsi seperti itu.
  • Hanya jika pewawancara terus meminta saya untuk menyelesaikan masalah yang diajukan, saya benar-benar akan mulai mencoba dan mencoret kode semu selama wawancara itu sendiri untuk mencoba dan mendapatkan semacam jawaban. Namun, saya tidak benar-benar berpikir saya akan melompat untuk mengambil pekerjaan itu jika pewawancara akan menjadi indikasi seperti apa perusahaan itu ...

Oh, jawaban ini menganggap wawancara itu untuk posisi terkait pemrograman C #. Tentu saja akan menjadi jawaban yang konyol jika wawancara itu untuk posisi terkait matematika. ;-)

peSHIr
sumber
7
Anda beruntung mereka meminta 32 int, jika 64 bit wawancara tidak akan pernah berlanjut setelah Anda menjalankan tes ;-)
alex2k8
Memang, jika saya bahkan sampai pada titik untuk benar-benar menulis tes itu dan menjalankannya selama wawancara. ;-) Maksud saya: Saya akan berusaha untuk tidak sampai ke titik itu dalam wawancara sama sekali. Pemrograman lebih dari "cara berpikir" daripada "bagaimana dia menulis baris kode" menurut saya.
RASHIr
7
Jangan ikuti saran ini dalam wawancara aktual. Pewawancara berharap Anda benar-benar menjawab pertanyaan itu. Mempertanyakan relevansi pertanyaan tidak akan memberi Anda apa-apa, tetapi hal itu dapat mengganggu pewawancara. Merancang tes sepele tidak membawa Anda selangkah lebih dekat ke jawabannya, dan Anda tidak dapat menjalankannya dalam wawancara. Jika Anda mendapatkan informasi tambahan (32 bit), cobalah mencari tahu bagaimana itu bisa berguna.
Stefan Haustein
Pewawancara yang kesal ketika saya meminta informasi lebih lanjut (sementara mungkin mempertanyakan relevansi pertanyaannya dalam proses) bukanlah pewawancara yang saya ingin bekerja untuk / dengan. Jadi saya akan terus mengajukan pertanyaan seperti itu dalam wawancara. Jika mereka tidak menyukainya, saya mungkin akan mengakhiri wawancara untuk berhenti membuang-buang waktu kita lebih jauh. Jangan suka pikiran "Saya hanya mengikuti perintah". Apakah kamu..?
RASHIr
16

Saya akan Anda mengubah 2 bit paling signifikan.

00.... => 01.... => 10.....

01.... => 10.... => 11.....

10.... => 11.... => 00.....

11.... => 00.... => 01.....

Seperti yang Anda lihat, itu hanya tambahan, meninggalkan bit yang dibawa.

Bagaimana saya mendapat jawaban? Pikiran pertama saya hanyalah kebutuhan akan simetri. 4 putaran untuk kembali ke tempat saya mulai. Pada awalnya saya pikir, itu kode 2bits Gray. Lalu saya pikir sebenarnya biner standar sudah cukup.

eipipuz
sumber
Masalah dengan pendekatan ini adalah bahwa itu tidak bekerja dengan angka negatif pujian dua (yang adalah apa yang digunakan setiap CPU modern). Itu sebabnya saya menghapus jawaban identik saya.
Tamas Czinege
Pertanyaan menentukan bilangan bulat bertanda 32-bit. Solusi ini tidak berfungsi untuk representasi dua-pelengkap atau pelengkap-satu dari bilangan bulat bertanda 32-bit. Ini hanya akan berfungsi untuk representasi sign-and-magnitude, yang sangat jarang di komputer modern (selain angka floating point).
Jeffrey L Whitledge
1
@DrJokepu - Wow, setelah enam bulan - sial!
Jeffrey L Whitledge
Tidakkah Anda hanya perlu mengubah angka menjadi representasi sign and magnitude di dalam fungsi, melakukan transformasi, lalu mengonversi kembali ke apa pun representasi bilangan bulat asli sebelum mengembalikannya?
Bill Michell
Saya suka bahwa Anda pada dasarnya menerapkan bilangan kompleks dengan memperkenalkan sedikit imajiner :)
jabirali
16

Berikut adalah solusi yang terinspirasi oleh persyaratan atau klaim bahwa bilangan kompleks tidak dapat digunakan untuk menyelesaikan masalah ini.

Mengalikan dengan akar kuadrat dari -1 adalah sebuah ide, yang sepertinya gagal karena -1 tidak memiliki akar kuadrat di atas bilangan bulat. Tetapi bermain-main dengan program seperti Mathematica memberi misalnya persamaan

(1849436465 2 +1) mod (2 32 -3) = 0.

dan ini hampir sama baiknya dengan memiliki akar kuadrat dari -1. Hasil dari fungsi harus berupa bilangan bulat yang ditandatangani. Oleh karena itu saya akan menggunakan mod operasi modulo yang dimodifikasi (x, n) yang mengembalikan integer y kongruen ke x modulo n yang paling dekat dengan 0. Hanya sedikit bahasa pemrograman yang memiliki operasi modulo, tetapi dapat dengan mudah didefinisikan . Misalnya dalam python adalah:

def mods(x, n):
    y = x % n
    if y > n/2: y-= n
    return y

Menggunakan persamaan di atas, masalah sekarang dapat diselesaikan sebagai

def f(x):
    return mods(x*1849436465, 2**32-3)

Ini memuaskan f(f(x)) = -xuntuk semua bilangan bulat dalam jangkauan . Hasil dari juga dalam kisaran ini, tetapi tentu saja perhitungan akan membutuhkan bilangan bulat 64-bit.[-231-2, 231-2]f(x)

Accipitridae
sumber
13

C # untuk rentang 2 ^ 32 - 1 angka, semua nomor int32 kecuali (Int32.MinValue)

    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

cetakan:

2147483647
3
2
1
0
-1
-2
-3
-2147483647
Pop Catalin
sumber
Ini juga tidak berfungsi untuk f (0) yaitu 1073741824. f (1073741824) = 0. f (f (1073741824)) = 1073741824
Dinah
Anda biasanya dapat membuktikan bahwa untuk dua ini tipe integer komplemen dari berbagai ukuran bit, fungsi harus tidak bekerja untuk setidaknya dua nilai masukan.
pemalas
12

Pada dasarnya fungsi harus membagi rentang yang tersedia menjadi siklus ukuran 4, dengan -n di ujung siklus n. Namun, 0 harus menjadi bagian dari siklus ukuran 1, karena jika tidak0->x->0->x != -x . Karena 0 sendirian, harus ada 3 nilai lain dalam rentang kami (yang ukurannya merupakan kelipatan 4) tidak dalam siklus yang tepat dengan 4 elemen.

Saya memilih nilai-nilai ekstra aneh ini menjadi MIN_INT, MAX_INT, dan MIN_INT+1. Selanjutnya, MIN_INT+1akan memetakan dengan MAX_INTbenar, tetapi terjebak di sana dan tidak memetakan kembali. Saya pikir ini adalah kompromi terbaik, karena ia hanya memiliki properti bagus dari nilai-nilai ekstrem yang tidak berfungsi dengan benar. Juga, itu berarti itu akan bekerja untuk semua BigInts.

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)
Strilanc
sumber
12

Tidak ada yang mengatakan itu harus tanpa kewarganegaraan.

int32 f(int32 x) {
    static bool idempotent = false;
    if (!idempotent) {
        idempotent = true;
        return -x;
    } else {
        return x;
    }
}

Curang, tapi tidak sebanyak contoh. Yang lebih jahat adalah dengan mengintip tumpukan untuk melihat apakah alamat pemanggil Anda adalah & f, tetapi ini akan menjadi lebih portabel (meskipun bukan utas aman ... versi utas aman akan menggunakan TLS). Yang lebih jahat:

int32 f (int32 x) {
    static int32 answer = -x;
    return answer;
}

Tentu saja, tak satu pun dari ini bekerja dengan baik untuk kasus MIN_INT32, tetapi ada sedikit yang berharga yang dapat Anda lakukan tentang hal itu kecuali Anda diizinkan untuk mengembalikan tipe yang lebih luas.

Christopher Smith
sumber
Anda dapat 'memutakhirkan' untuk menanyakan tentang alamat (ya, Anda harus mendapatkannya dengan ref \ sebagai pointer) - dalam C, misalnya: int f (int & n) {static int * addr = & n; if (addr == & n) {return -n; } mengembalikan n; }
IUnknownPointer
11

Saya bisa membayangkan menggunakan bit ke-31 sebagai bit imajiner ( i ) akan menjadi pendekatan yang akan mendukung setengah rentang total.

llamaoo7
sumber
Ini akan menjadi lebih kompleks tetapi tidak lebih efektif daripada jawaban terbaik saat ini
1800 INFORMASI
1
@ 1800 INFORMASI: Di sisi lain, domain [-2 ^ 30 + 1, 2 ^ 30-1] berdekatan yang lebih menarik dari sudut pandang matematika.
Jochen Walter
10

bekerja untuk 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
}
MartinStettner
sumber
10

Masalahnya menyatakan "integer bertanda 32-bit" tetapi tidak menentukan apakah keduanya komplemen dua atau satu .

Jika Anda menggunakan komplemen satu maka semua nilai 2 ^ 32 terjadi dalam siklus dengan panjang empat - Anda tidak memerlukan kasing khusus untuk nol, dan Anda juga tidak memerlukan persyaratan.

Dalam C:

int32_t f(int32_t x)
{
  return (((x & 0xFFFFU) << 16) | ((x & 0xFFFF0000U) >> 16)) ^ 0xFFFFU;
}

Ini bekerja dengan

  1. Saling menukar blok 16-bit tinggi dan rendah
  2. Menghindari salah satu blok

Setelah dua lintasan kami memiliki bitwise kebalikan dari nilai aslinya. Yang dalam representasi satu komplemen sama dengan negasi.

Contoh:

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)
finnw
sumber
1
Bagaimana dengan byte-order di berbagai arsitektur?
Steven
1
Semua aritmatika adalah 32-bit. Saya tidak memanipulasi byte individu, jadi urutan byte tidak akan mempengaruhinya.
finnw
Ini kedengarannya cukup dekat. Anda dapat menganggap inputnya adalah 2-pelengkap. Jadi Anda mengonversi ke representasi bit tanda. Sekarang tergantung pada bit terakhir, Anda membalik bit pertama dan bit terakhir atau hanya bit terakhir. Pada dasarnya Anda hanya meniadakan angka genap dan siklus genap / ganjil sepanjang waktu. Jadi, Anda kembali dari aneh ke aneh dan bahkan ke setelah 2 panggilan. Pada akhirnya Anda mengonversi kembali ke 2-pelengkap. Telah memposting kode untuk ini di suatu tempat di bawah ini.
Stefan Haustein
9

: D

boolean inner = true;

int f(int input) {
   if(inner) {
      inner = false;
      return input;
   } else {
      inner = true;
      return -input;
   }
}
Drew
sumber
5
Mungkin juga membuat Anda berdiskusi tentang mengapa variabel global buruk jika mereka tidak mengeluarkan Anda dari wawancara di sana!
palswim
9
return x ^ ((x%2) ? 1 : -INT_MAX);
Mike Meehan
sumber
7

Saya ingin berbagi pandangan saya tentang masalah menarik ini sebagai ahli matematika. Saya pikir saya punya solusi paling efisien.

Jika saya ingat dengan benar, Anda meniadakan integer 32-bit yang ditandatangani dengan hanya membalik bit pertama. Misalnya, jika n = 1001 1101 1110 1011 1110 0000 1110 1010, maka -n = 0001 1101 1110 1011 1110 0000 1110 1010.

Jadi bagaimana kita mendefinisikan fungsi f yang mengambil bilangan bulat 32-bit yang ditandatangani dan mengembalikan bilangan bulat 32-bit lainnya dengan properti yang mengambil f dua kali sama dengan membalik bit pertama?

Biarkan saya ulangi pertanyaannya tanpa menyebutkan konsep aritmatika seperti bilangan bulat.

Bagaimana kita mendefinisikan fungsi f yang mengambil urutan nol dan yang panjang 32 dan mengembalikan urutan nol dan yang sama panjang, dengan properti yang mengambil f dua kali sama dengan membalik bit pertama?

Pengamatan: Jika Anda dapat menjawab pertanyaan di atas untuk kasing 32 bit, maka Anda juga dapat menjawab kasing 64 bit, kasing 100 bit, dll. Anda tinggal menerapkan f ke bit 32 pertama.

Sekarang jika Anda dapat menjawab pertanyaan untuk case 2 bit, Voila!

Dan ya ternyata mengubah 2 bit pertama sudah cukup.

Ini kode semu

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.

Catatan: Langkah 2 dan langkah 3 bersama-sama dapat disingkat sebagai (a, b) -> (-b, a). Terlihat tidak asing? Itu akan mengingatkan Anda tentang rotasi 90 derajat pesawat dan perkalian dengan akar kuadrat dari -1.

Jika saya hanya menyajikan pseudo-code saja tanpa pembuka yang lama, itu akan terlihat seperti kelinci, saya ingin menjelaskan bagaimana saya mendapatkan solusinya.

Yoo
sumber
6
Ya itu masalah yang menarik. Anda tahu matematika Anda. Tapi ini masalah ilmu komputer. Jadi, Anda perlu belajar komputer. Representasi sign-magnitude diijinkan tetapi keluar dari gaya sekitar 60 tahun yang lalu. 2-pelengkap paling populer.
Pemrogram Windows
5
Inilah yang fungsi Anda lakukan pada dua bit ketika diterapkan dua kali: (a, b) -> (-b, a) -> (-a, -b). Tapi, kami mencoba untuk mencapai (-a, b), bukan (-a, -b).
buti-oxa
@ buti-oxa, kamu benar. Operasi dua bit harus berjalan seperti: 00 -> 01 -> 10 -> 11 -> 00. Tapi kemudian algoritma saya mengasumsikan representasi sign-magnitude yang tidak populer sekarang, seperti yang dikatakan oleh programmer Windows, jadi saya pikir algoritma saya kurang bermanfaat. .
Yoo
Jadi tidak bisakah dia hanya melakukan langkah dua kali, bukan satu kali?
Nosredna
4
buti-oxa sepenuhnya benar: fungsinya bahkan tidak membalik bit pertama setelah dua doa, itu membalik dua bit pertama. Membalik semua bit lebih dekat dengan apa yang dilakukan komplemen 2, tetapi itu tidak sepenuhnya benar.
redtuna