Nonstabilizerness or magic resource characterizes the amount of non-Clifford operations needed to prepare quantum states. It is a crucial resource for quantum computing and a necessary condition for quantum advantage. However, quantifying magic resource beyond a few qubits has been a major challenge. Here, we introduce efficient measures of magic resource for pure quantum states with a sampling cost that is independent of the number of qubits. Our method uses Bell measurements over two copies of a state, which we implement in experiment together with a cost-free error-mitigation scheme. We show the transition of classically simulable stabilizer states into intractable quantum states on the IonQ quantum computer. For applications, we efficiently distinguish stabilizer and nonstabilizer states with low measurement cost even in the presence of experimental noise. Further, we propose a variational quantum algorithm to maximize our measure via the shift rule. Our algorithm can be free of barren plateaus even for highly expressible variational circuits. Finally, we experimentally demonstrate a Bell-measurement protocol for the stabilizer Rényi entropy as well as the Wallach-Meyer entanglement measure. Our results pave the way to understanding the nonclassical power of quantum computers, quantum simulators, and quantum many-body systems.