ฉันพบฟังก์ชันที่คำนวณกำลังสองของตัวเลขแล้ว:
int p(int n) {
int a[n]; //works on C99 and above
return (&a)[n] - a;
}
ส่งกลับค่า n2 คำถามคือ มันทำแบบนั้นได้อย่างไร? หลังจากการทดสอบเล็กน้อย ฉันพบว่าระหว่าง (&a)[k] ถึง (&a)[k+1] คือ sizeof(a)/sizeof(int) ทำไมเป็นอย่างนั้น?
แน่นอนว่าเป็นการแฮ็ก... แต่เป็นวิธีการยกกำลังสองตัวเลขโดยไม่ใช้ตัวดำเนินการ * (นี่คือข้อกำหนดของการแข่งขันเขียนโค้ด)
(&a)[n]
เทียบเท่ากับตัวชี้ไปที่ int ที่ตำแหน่ง
(a + sizeof(a[n])*n)
และด้วยเหตุนี้สำนวนทั้งหมดจึงเป็นเช่นนั้น
(&a)[n] -a
= (a + sizeof(a[n])*n -a) /sizeof(int)
= sizeof(a[n])*n / sizeof(int)
= sizeof(int) * n * n / sizeof(int)
= n * n
(&a) เป็นตัวชี้ไปยังอ็อบเจ็กต์ n*sizeof(int) เมื่อ n ไม่เป็นที่รู้จักในเวลาคอมไพล์ C เคยเป็นภาษา ง่าย...
- person Floris; 08.01.2015
* ในโค้ด คุณสามารถตัดสินใจได้ว่านั่นหมายความว่าอย่างไร มันเป็นความท้าทายที่โง่เขลา
- person Mark Lakata; 09.01.2015
* มีมากกว่าหนึ่งความหมายในภาษา C คุณควรระบุเฉพาะเกี่ยวกับตัวดำเนินการ การคูณ เมื่อมองแวบแรก ฉันคิดว่าคุณกำลังพูดถึงตัวดำเนินการทางอ้อมแต่ก็เข้าใจเมื่อเข้าไปที่ลิงก์
- person haccks; 09.01.2015
เพื่อทำความเข้าใจแฮ็กนี้ ก่อนอื่นคุณต้องเข้าใจความแตกต่างของพอยน์เตอร์ กล่าวคือ จะเกิดอะไรขึ้นเมื่อพอยน์เตอร์สองตัวที่ชี้ไปยังองค์ประกอบของ อาร์เรย์เดียวกัน ถูกลบออก
เมื่อลบพอยน์เตอร์ตัวหนึ่งออกจากอีกพอยน์เตอร์ ผลลัพธ์ที่ได้คือระยะห่าง (วัดในองค์ประกอบอาร์เรย์) ระหว่างพอยน์เตอร์เหล่านั้น ดังนั้น หาก p ชี้ไปที่ a[i] และ q ชี้ไปที่ a[j] ดังนั้น p - q จะเท่ากับ i - j
เมื่อลบพอยน์เตอร์สองตัว ทั้งสองจะชี้ไปที่องค์ประกอบของออบเจ็กต์อาร์เรย์เดียวกัน หรือหนึ่งตัวเลยองค์ประกอบสุดท้ายของออบเจ็กต์อาร์เรย์ ผลลัพธ์คือความแตกต่างของตัวห้อยขององค์ประกอบอาร์เรย์ทั้งสอง [...].
กล่าวอีกนัยหนึ่ง หากนิพจน์PและQชี้ไปที่องค์ประกอบi-th และj-th ของออบเจ็กต์อาร์เรย์ ตามลำดับ นิพจน์(P)-(Q)จะมีค่าi−jโดยให้ค่าพอดีกับวัตถุประเภทptrdiff_t
ตอนนี้ฉันคาดหวังว่าคุณจะทราบถึงการแปลงชื่ออาร์เรย์เป็นตัวชี้ a แปลงเป็นตัวชี้เป็นองค์ประกอบแรกของอาร์เรย์ a &a คือที่อยู่ของบล็อกหน่วยความจำทั้งหมด กล่าวคือ เป็นที่อยู่ของอาร์เรย์ a รูปด้านล่างจะช่วยให้คุณเข้าใจ (อ่าน คำตอบนี้ สำหรับคำอธิบายโดยละเอียด):
นี่จะช่วยให้คุณเข้าใจว่าเหตุใด a และ &a จึงมีที่อยู่เดียวกัน และ (&a)[i] เป็นที่อยู่ของอาร์เรย์ที่ ith อย่างไร (ที่มีขนาดเท่ากับของ a)
ดังนั้นแถลงการณ์
return (&a)[n] - a;
เทียบเท่ากับ
return (&a)[n] - (&a)[0];
และความแตกต่างนี้จะให้จำนวนองค์ประกอบระหว่างพอยน์เตอร์ (&a)[n] และ (&a)[0] ซึ่งเป็นอาร์เรย์ n แต่ละองค์ประกอบจาก n int องค์ประกอบ ดังนั้น องค์ประกอบอาร์เรย์ทั้งหมดคือ n*n = n2
หมายเหตุ:
เมื่อลบพอยน์เตอร์สองตัว ทั้งสองจะต้องชี้ไปที่องค์ประกอบของออบเจ็กต์อาร์เรย์เดียวกัน หรือหนึ่งตัวเลยองค์ประกอบสุดท้ายของออบเจ็กต์อาร์เรย์; ผลลัพธ์คือความแตกต่างของตัวห้อยขององค์ประกอบอาร์เรย์ทั้งสอง ขนาดของผลลัพธ์เป็นแบบกำหนดการใช้งาน และประเภทของผลลัพธ์ (ประเภทจำนวนเต็มที่ลงนาม) คือ
ptrdiff_tที่กำหนดไว้ในส่วนหัว<stddef.h>หากผลลัพธ์ไม่สามารถแสดงในออบเจ็กต์ประเภทนั้นได้ แสดงว่าพฤติกรรมนั้นไม่ได้ถูกกำหนดไว้
เนื่องจาก (&a)[n] ไม่ได้ชี้ไปที่องค์ประกอบของออบเจ็กต์อาร์เรย์เดียวกันหรือไม่ได้ชี้ไปที่องค์ประกอบสุดท้ายของออบเจ็กต์อาร์เรย์ (&a)[n] - a จะเรียกใช้ พฤติกรรมที่ไม่ได้กำหนด
โปรดทราบว่าควรเปลี่ยนประเภทการส่งคืนของฟังก์ชัน p เป็น ptrdiff_t จะดีกว่า
&a[k] เป็นที่อยู่ขององค์ประกอบที่ k ของอาร์เรย์ a (&a)[k] จะถือเป็นที่อยู่ของอาร์เรย์ขององค์ประกอบ k เสมอ ดังนั้น องค์ประกอบแรกอยู่ที่ตำแหน่ง a (หรือ &a) องค์ประกอบที่สองอยู่ที่ตำแหน่ง a + (จำนวนองค์ประกอบของอาร์เรย์ a ซึ่งก็คือ n)*(ขนาดขององค์ประกอบอาร์เรย์) และอื่นๆ และโปรดทราบว่าหน่วยความจำสำหรับอาร์เรย์ที่มีความยาวผันแปรได้จะถูกจัดสรรบนสแต็ก ไม่ใช่บนฮีป
- person haccks; 08.01.2015
(&a)[n]-(&a)[0] จะเป็นวิธีที่ถูกต้องในการทำเช่นนี้หรือไม่
- person Floris; 08.01.2015
(&a)[n] กำลังละเมิดกฎที่มาตรฐานระบุว่า: ทั้งคู่จะต้องชี้ไปที่องค์ประกอบของออบเจ็กต์อาร์เรย์เดียวกัน หรือหนึ่งรายการที่อยู่เลยองค์ประกอบสุดท้ายของออบเจ็กต์อาร์เรย์ คุณสามารถทำได้ในวิธีที่ถูกต้องโดยเปลี่ยนเนื้อหาของฟังก์ชันเป็น return sizeof (char [n][n]); ตามที่แนะนำใน ความคิดเห็นนี้
- person haccks; 08.01.2015
a[n-1] a[n] เป็นหนึ่งในองค์ประกอบสุดท้ายของอาร์เรย์ (&a)[1] เป็นตัวชี้ไปยังองค์ประกอบสุดท้าย (อาร์เรย์ของ n int) ของอาร์เรย์
- person haccks; 14.01.2015
a เป็นอาร์เรย์ (ตัวแปร) ของ n int
&a เป็นตัวชี้ไปยังอาร์เรย์ (ตัวแปร) ของ n int
(&a)[1] เป็นตัวชี้ของ int หนึ่ง int ที่ผ่านมาองค์ประกอบอาร์เรย์สุดท้าย ตัวชี้นี้คือ n int องค์ประกอบหลัง &a[0]
(&a)[2] เป็นตัวชี้ของ int หนึ่ง int ที่ผ่านมาองค์ประกอบอาร์เรย์สุดท้ายของสองอาร์เรย์ ตัวชี้นี้คือองค์ประกอบ 2 * n int หลัง &a[0]
(&a)[n] เป็นตัวชี้ของ int หนึ่ง int ที่ผ่านมาองค์ประกอบอาร์เรย์สุดท้ายของอาร์เรย์ n ตัวชี้นี้คือ n * n int องค์ประกอบหลัง &a[0] เพียงลบ &a[0] หรือ a แล้วคุณจะได้ n
แน่นอนว่านี่เป็นพฤติกรรมที่ไม่ได้กำหนดในทางเทคนิคแม้ว่าจะทำงานบนเครื่องของคุณเนื่องจาก (&a)[n] ไม่ได้ชี้ภายในอาร์เรย์หรือหนึ่งจุดผ่านองค์ประกอบอาร์เรย์สุดท้าย (ตามที่กำหนดโดยกฎ C ของเลขคณิตของตัวชี้)
[n] ไวยากรณ์จะประกาศอาร์เรย์และอาร์เรย์จะสลายตัวเป็นพอยน์เตอร์ ประโยชน์สามประการที่แยกจากกันพร้อมกับผลที่ตามมานี้
- person Tommy; 08.01.2015
(&a)[n] เป็นประเภท int[n] และ นั้น แสดงเป็น int* เนื่องจากอาร์เรย์แสดงเป็นที่อยู่ขององค์ประกอบแรก ในกรณีที่คำอธิบายไม่ชัดเจน
- person WhozCraig; 08.01.2015
หากคุณมีพอยน์เตอร์สองตัวที่ชี้ไปยังสององค์ประกอบของอาร์เรย์เดียวกัน ความแตกต่างจะทำให้ได้จำนวนองค์ประกอบระหว่างพอยน์เตอร์เหล่านี้ ตัวอย่างเช่น ข้อมูลโค้ดนี้จะส่งออกเป็น 2
int a[10];
int *p1 = &a[1];
int *p2 = &a[3];
printf( "%d\n", p2 - p1 );
ตอนนี้ให้พิจารณาการแสดงออก
(&a)[n] - a;
ในนิพจน์นี้ a มีประเภท int * และชี้ไปที่องค์ประกอบแรก
นิพจน์ &a มีประเภท int ( * )[n] และชี้ไปที่แถวแรกของอาร์เรย์สองมิติที่อิมเมจ ค่าของมันตรงกับค่าของ a แม้ว่าประเภทจะแตกต่างกันก็ตาม
( &a )[n]
เป็นองค์ประกอบที่ n ของอาร์เรย์สองมิติที่ทำอิมเมจนี้ และมีประเภท int[n] นั่นคือแถวที่ n ของอาร์เรย์อิมเมจ ในนิพจน์ (&a)[n] - a จะถูกแปลงเป็นที่อยู่ขององค์ประกอบแรกและมีประเภท `int *
ดังนั้นระหว่าง (&a)[n] ถึง a จะมี n แถวที่มี n องค์ประกอบ ดังนั้นผลต่างจะเท่ากับ n * n
Expression | Value | Explanation
a | a | point to array of int elements
a[n] | a + n*sizeof(int) | refer to n-th element in array of int elements
-------------------------------------------------------------------------------------------------
&a | a | point to array of (n int elements array)
(&a)[n] | a + n*sizeof(int[n]) | refer to n-th element in array of (n int elements array)
-------------------------------------------------------------------------------------------------
sizeof(int[n]) | n * sizeof(int) | int[n] is a type of n-int-element array
ดังนั้น,
(&a)[n] คือตัวชี้ int[n]a คือตัวชี้ intตอนนี้นิพจน์ (&a)[n]-a ทำการลบตัวชี้:
(&a)[n]-a
= ((a + n*sizeof(int[n])) - a) / sizeof(int)
= (n * sizeof(int[n])) / sizeof(int)
= (n * n * sizeof(int)) / sizeof(int)
= n * n
int p(n)? นั่นมันคอมไพล์ด้วยเหรอ? - person barak manos schedule 08.01.2015gcc- person lurker schedule 08.01.2015int q(int n) { return sizeof (char [n][n]); }- person ouah schedule 08.01.2015sizeofคือการบันทึกอักขระ คนอื่นๆ: นี่เป็นโค้ดที่คลุมเครือโดยเจตนา มันเป็นพฤติกรรมที่ไม่ได้กำหนดไว้ คำตอบของ @ouah นั้นถูกต้อง - person ecatmur schedule 08.01.2015O(n^2)เพื่อคำนวณn^2- person Khaled.K schedule 14.01.2015